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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Если 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.


См. также[править | править исходный текст]