|
|
 |
Условие
Таня последовательно выписывала числа вида ${n^7-1}$ для натуральных чисел $n=2,3,\ldots$ и заметила, что при $n=8$ полученное число делится на 337. А при каком наименьшем $n\gt 1$ она получит число, делящееся на 2022?Решение
Пусть натуральное число $n$ таково, что $n^7-1$ делится на $2022=2\cdot 3\cdot 337$. Тогда $n^7-1$ делится на 2 и на 3, поэтому $n$ – нечётное число, имеющее остаток 1 при делении на 3. Помимо того, $n^7-1$ делится на 337. Заметим, что если два числа сравнимы по модулю 337 (т.е. дают одинаковые остатки при делении на 337), то седьмые степени этих чисел также сравнимы по модулю 337. Это означает, что для нахождения искомого числа достаточно рассмотреть все целые числа $n$ из промежутка $[0;336]$, удовлетворяющие сравнению $n^7 \equiv 1 \pmod{337}$.Мы будем пользоваться следующим утверждением. Пусть $p$ – простое число, $P_k$ – многочлен степени $k$ с целыми коэффициентами, старший коэффициент которого не делится на $p$; тогда сравнение $P_k(n)\equiv 0\pmod p$ имеет не более $k$ решений среди целых чисел $0\leqslant n < p$. (Доказать это утверждение можно индукцией по степени $k$, примерно так же, как то, что многочлен степени $k$ с вещественными коэффициентами имеет не более $k$ вещественных корней. См. также статью А. Геронимуса «Сравнения по простому модулю» в Кванте №11 за 1978 год.)
Найдём теперь все решения сравнения $n^7\equiv 1\pmod{337}$ на отрезке $[0;336]$. Нам известны два решения: $n_1=1$, $n_2=8$. Заметим, что если $n$ – решение сравнения $n^7 \equiv 1 \pmod{337}$, то для любого натурального $s$ числа $n^s$ также являются решениями. Следовательно, решениями данного сравнения являются числа \begin{align*} 8^2&=64\equiv 64 \pmod{337},\\ 8^3&=512\equiv 175 \pmod{337},\\ 8^4&\equiv 8\cdot 175\equiv 52 \pmod{337},\\ 8^5&\equiv 8\cdot 52\equiv 79 \pmod{337},\\ 8^6&\equiv 8\cdot 79\equiv 295 \pmod{337}. \end{align*}
Итак, мы нашли семь решений на отрезке $[0;336]$: $n_1=1$, $n_2=8$,
$n_3=52$, $n_4=64$, $n_5=79$, $n_6=175$, $n_7=295$. Так как число 337 простое, по сформулированному выше утверждению других решений на этом отрезке нет. Из них нечётными и имеющими остаток 1 при делении на 3 являются $n_1=1$, $n_5=79$, $n_6=175$ и $n_7=295$. Из них наименьшее, большее 1, есть $n_5=79$.
