Задача из журнала «Квант»(2002 год, 2 выпуск)

Условие

Пусть $a$, $m_1$, $m_2$ $-$ натуральные числа, причем $a$ взаимно просто как с $m_1$, так и с $m_2$. Обозначим через $r_n$ остаток от деления целой части числа $\frac{a^n}{m_1}$ на $m_2$ $(n = 0, 1, 2, \ldots)$.

Докажите, что последовательность $\{r_n\}$ является периодической.

Доказательство

Так как НОД$(a$, $m_1)$ $=$ НОД$(a$, $m_2) = 1$, то НОД$(a$, $m_1m_2) = 1$. Пусть $n_0 -$ какое-нибудь натуральное число, для которого $a^{n_0}$ при делении на $m_1m_2$ дает в остатке $1$. (Если НОД$(a$, $m_1m_2) = 1$, то такое число обязательно существует. Можно, например, положить $n_0 = \varphi(m_1m_2)$, где $\varphi(m) —$ функция Эйлера $-$ см. статью В.Сендерова и А.Спивака «Малая теорема Ферма» в «Кванте» №1 за 2000 год.)

Тогда $a^{n_0} = Qm_1m_2 + 1$ для некоторого целого числа $Q$. Теперь при любом $n \geqslant n_0$ имеем

$$\left[\frac{a^n}{m_1}\right] = \left[\frac{a^{n_0}a^{n-n_0}}{m_1}\right] = \left[\frac{(Qm_1m_2 + 1)a^{n-n_0}}{m_1}\right] =$$ $$= \left[a^{n-n_0}Qm_2 + \frac{a^{n-n_0}}{m_1}\right] = a^{n-n_0}Qm_2 + \left[\frac{a^{n-n_0}}{m_1}\right]$$ ($\left[x\right]$ обозначает целую часть числа $x$).

Таким образом, остатки чисел $\left[\frac{a^n}{m_1}\right]$ и $\left[\frac{a^{n-n_0}}{m_1}\right]$ при делении на $m_2$ совпадают, т.е. $r_n = r_{n-n_0}$. Значит, последовательность $\{r_n\}$ имеет период длины $n_0$ (доказано также и то, что этот период начинается с самого начала последовательности).

Возникает вопрос о длине наименьшего периода последовательности $\{r_n\}$. Верно ли, что если в качестве $n_0$ взять наименьшее натуральное число такое, что $a^{n_0}$ при делении на $m_1m_2$ дает в остатке $1$, то $n_0$ и будет длиной наименьшего периода? Как показывает пример $a = 3$, $m_1 = 13$, $m_2 = 2$ (здесь $n_0 = 3$, а последовательность $\{r_n\}$ сплошь состоит из нулей), ответ на этот вопрос в общем случае отрицателен. Однако если дополнительно предположить, например, что $m_2 \geqslant m_1$, то ответ будет утвердительным (читателю предлагается доказать это в качестве упражнения).

Н.Осипов