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

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

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

В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю ${\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  (англ.)

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Проставить сноски, внести более точные указания на источники. Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.