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

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

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

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

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

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

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

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

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

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

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

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

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

или

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

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

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

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

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

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

или

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

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

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

или

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

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

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