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

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

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

Частным случаем теоремы Эйлера является малая теорема Ферма (при простом 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$. ■

См. также

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