Пример использования теоремы Эйлера

Если число $a$, т.е. в этом случае $a = 3$, и модуль $m$ взаимно просты (здесь $m = 100$), тогда существует такое натуральное число $k > 0$, для которого верно следующее сравнение: \[a^{k} \equiv 1 \; (\mkern-18mu \mod m) \; \; (*)\] Действительно, теорема Эйлера говорит, что выше представленное сравнение верно для $k = \phi(m)$, где $\phi(n)$ это функция Эйлера и ей значение определяется для любого натурального $n$ как количество чисел меньших либо равных $n$ и взаимно простых с ним. Самое интересное, что $\phi(m)$ часто не единственное число при котором сравнение (*) верно. В самом деле, нынешняя задача является примером такого случая, в котором равенство выполняется тоже для числа гораздо меньшего $\phi(m)$.

Почему существование такого натурального числа $k > 0$, что для взаимно простых $a$ i $m$ имеется \[a^{k} \equiv 1 \; (\mkern-18mu \mod m)\] настолько важно? Потому, что тогда для вычисления \[a^{n} \mkern-18mu \mod m\] хватит принять \[a^{n \mkern-8mu \mod k} \mkern-18mu \mod m\] поскольку если $n = sk + r$ для натуральных $s > 0$ и $0 \leq r < k$, тогда получаем \[(a^{k})^{s} \equiv 1 \; (\mkern-18mu \mod m)\] т.е. \[a^{sk} \equiv 1 \; (\mkern-18mu \mod m)\] умножая сравнение на $a^{r}$ преображаем её в следующее \[a^{sk}*a^{r} \equiv a^{r} \; (\mkern-18mu \mod m)\] и из этого \[a^{sk+r} \equiv a^{r} \; (\mkern-18mu \mod m)\] пользуясь равенством $n = sk + r$ можем представить сравнение в таком вот виде: \[a^{n} \equiv a^{n \mkern-8mu \mod k} \; (\mkern-18mu \mod m)\] Полученное свойство позволяет уменьшить показатели до такого уровня, который даёт возможность выполнить операцию потенцирования даже с помощью обычного карманного калькулятора.

Исходя из определения функции Эйлера вычислим теперь значение $\phi(100)$: \[\phi(100) = 100\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 100\frac{1}{2}\frac{4}{5} = 40\] следовательно \[3^{3333333} \equiv 3^{3333333 \mod 40}\; (\mkern-18mu \mod 100)\] т.е. \[3^{3333333} \equiv 3^{13} = 1594323 \; (\mkern-18mu \mod 100)\] и в итоге получаем \[3^{3333333} \equiv 23 \; (\mkern-18mu \mod 100)\]

Надо здесь заметить, что если бы мы хотели найти наугад наименьший показатель $k > 0$, для которого верно \[3^{k} \equiv 1 \; (\mkern-18mu \mod 100) \; \; (**)\] то тогда хватило бы проверить только $20$ начальных натуральных чисел. Действительно \[3^{20} = 3486784401 \equiv 1 \; (\mkern-18mu \mod 100)\] Представленная здесь задача является примером ситуации, когда функция Эйлера не гарантирует получения наименьшего возможного числа при котором верное сравнение (**).

В таблице помещенной ниже, содержащей степени тройки для всех показателей от $1$ до $20$ с соответствующими им остатками с деления на $100$, любопытный читатель сможет самостоятельно проверить правдивость выше написанного: