Теорема Эйлера (теория чисел)

Теоре́ма Э́йлера в теории чисел гласит: Шаблон:Рамка Если $a$ и $m$ взаимно просты, то $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$, где $\phi (m)$ — функция Эйлера. Шаблон:Конец рамки

Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма: Шаблон:Рамка Если $a$ не делится на простое число $p$, то $a^{p-1}\equiv 1(\mathrm{mod}p)$. Шаблон:Конец рамки

В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю $m$.

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

С помощью теории чисел

Пусть $x_1,\dots ,x_{\phi (m)}$ — все различные натуральные числа, меньшие $m$ и взаимно простые с ним.

Рассмотрим все возможные произведения $x_{i}a$ для всех $i$ от $1$ до $\phi (m)$.

Поскольку $a$ взаимно просто с $m$, и $x_i$ взаимно просто с $m$, то и $x_{i}a$ также взаимно просто с $m$, то есть $x_{i}a\equiv x_j(\mathrm{mod}m)$ для некоторого $j$.

Отметим, что все остатки $x_{i}a$ при делении на $m$ различны. Действительно, пусть это не так, тогда существуют такие $i_1\ne i_2$, что

$x_{i_1}a\equiv x_{i_2}a(\mathrm{mod}m)$

или

$(x_{i_1}-x_{i_2})a\equiv 0(\mathrm{mod}m).$

Так как $a$ взаимно просто с $m$, то последнее равенство равносильно тому, что

$x_{i_1}-x_{i_2}\equiv 0(\mathrm{mod}m)$ или $x_{i_1}\equiv x_{i_2}(\mathrm{mod}m)$.

Это противоречит тому, что числа $x_1,\dots ,x_{\phi (m)}$ попарно различны по модулю $m$.

Перемножим все сравнения вида $x_{i}a\equiv x_j(\mathrm{mod}m)$. Получим:

$x_1\cdots x_{\phi (m)}{a}^{\phi (m)}\equiv x_1\cdots x_{\phi (m)}(\mathrm{mod}m)$

или

$x_1\cdots x_{\phi (m)}(a^{\phi (m)}-1)\equiv 0(\mathrm{mod}m)$.

Так как число $x_1\cdots x_{\phi (m)}$ взаимно просто с $m$, то последнее сравнение равносильно тому, что

$a^{\phi (m)}-1\equiv 0(\mathrm{mod}m)$

или

$a^{\phi (m)}\equiv 1(\mathrm{mod}m).$ Шаблон:ЧТД

С помощью теории групп

Рассмотрим мультипликативную группу ${\mathbb{Z}}_n^{\ast }$ обратимых элементов кольца вычетов ${\mathbb{Z}}_n$. Её порядок равен $\phi (n)$ согласно определению функции Эйлера. Поскольку число $a$ взаимно просто с $n$, соответствующий ему элемент $\bar{a}$ в ${\mathbb{Z}}_n$ является обратимым и принадлежит ${\mathbb{Z}}_n^{\ast }$. Элемент $\bar{a}\in {\mathbb{Z}}_n^{\ast }$ порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит $\phi (n)$, отсюда $a^{\phi (n)}=\bar{1}$. Шаблон:ЧТД

См. также

• Список объектов, названных в честь Леонарда Эйлера

Литература

• Шаблон:Книга

Ссылки

• Topics: Euler’s Theorem, Chinese Remainder Theorem, Amir Kamil, CS70, Fall 2003. UC Berkeley Шаблон:Ref-en
• RSA and the Chinese remainder theorem / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley Шаблон:Ref-en