Загрузка
Английский
Польский
Домашняя страница Николая Гайдука

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

Д
опустим, нас попросили определить значение следующей формулы: \[3^{3333333} \mod 100\] то есть нам нужно найти остаток от деления $3^{3333333}$ на $100$. Иначе говоря, нас интересуют последние две цифры десятичной репрезентации числа $3^{3333333}$. На первый взгляд проблема является не очень привлекательной с арифметической точки зрения; может оказаться, что перед нами много тяжёлой и не совсем поучительной работы. Как мы увидим в следующих частях нынешней статьи, задачи такого типа часто решаются с помощью своего рода "быстрых переходов", путём которых мы можем легко достигнуть желаемые результаты.

Если число $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$, любопытный читатель сможет самостоятельно проверить правдивость выше написанного:

$k$$3^{k}$$3^{k} \mod 100$
$1$$3$$3$
$2$$9$$9$
$3$$27$$27$
$4$$81$$81$
$5$$243$$43$
$6$$729$$29$
$7$$2187$$87$
$8$$6561$$61$
$9$$19683$$83$
$10$$59049$$49$
$11$$177147$$47$
$12$$531441$$41$
$13$$1594323$$23$
$14$$4782969$$69$
$15$$14348907$$7$
$16$$43046721$$21$
$17$$129140163$$63$
$18$$387420489$$89$
$19$$1162261467$$67$
$20$$3486784401$$1$
© 2007-2014, Mikołaj Hajduk