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

Если ${\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 {\overline {a}}^{\varphi (n)}={\overline {1}}}$ . ■

См. также

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

Литература

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

Ссылки

• , Amir Kamil, CS70, Fall 2003. UC Berkeley (англ.)
• / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley (англ.)