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

Теоре́ма Э́йлера в теории чисел гласит:

Если $a$ и $m$ взаимно просты, то $a^{\varphi (m)}\equiv 1{\pmod {m}}$, где $\varphi (m)$ — функция Эйлера.

Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма:

Если $a$ не делится на простое число $p$, то $a^{p-1}\equiv 1{\pmod {p}}$.

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

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

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

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

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

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

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

$x_{i_{1}}a\equiv x_{i_{2}}a{\pmod {m}}$

или

$(x_{i_{1}}-x_{i_{2}})a\equiv 0{\pmod {m}}.$

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

$x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}$ или $x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}$.

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

Перемножим все сравнения вида $x_{i}a\equiv x_{j}{\pmod {m}}$. Получим:

$x_{1}\cdots x_{\varphi (m)}a^{\varphi (m)}\equiv x_{1}\cdots x_{\varphi (m)}{\pmod {m}}$

или

$x_{1}\cdots x_{\varphi (m)}(a^{\varphi (m)}-1)\equiv 0{\pmod {m}}$.

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

$a^{\varphi (m)}-1\equiv 0{\pmod {m}}$

или

$a^{\varphi (m)}\equiv 1{\pmod {m}}.$ ■

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

Рассмотрим мультипликативную группу $\mathbb {Z} _{n}^{*}$ обратимых элементов кольца вычетов $\mathbb {Z} _{n}$. Её порядок равен $\varphi (n)$ согласно определению функции Эйлера. Поскольку число $a$ взаимно просто с $n$, соответствующий ему элемент ${\overline {a}}$ в $\mathbb {Z} _{n}$ является обратимым и принадлежит $\mathbb {Z} _{n}^{*}$. Элемент ${\overline {a}}\in \mathbb {Z} _{n}^{*}$ порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит $\varphi (n)$, отсюда ${\overline {a}}^{\varphi (n)}={\overline {1}}$. ■

См. также

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

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.

Ссылки

• Topics: Euler’s Theorem, Chinese Remainder Theorem, Amir Kamil, CS70, Fall 2003. UC Berkeley  (англ.)
• RSA and the Chinese remainder theorem / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley  (англ.)