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

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

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

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

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

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

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

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

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

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

Поскольку [math]\displaystyle{ a }[/math] взаимно просто с [math]\displaystyle{ m }[/math], и [math]\displaystyle{ x_i }[/math] взаимно просто с [math]\displaystyle{ m }[/math], то и [math]\displaystyle{ x_i a }[/math] также взаимно просто с [math]\displaystyle{ m }[/math], то есть [math]\displaystyle{ x_i a \equiv x_j\pmod m }[/math] для некоторого [math]\displaystyle{ j }[/math].

Отметим, что все остатки [math]\displaystyle{ x_i a }[/math] при делении на [math]\displaystyle{ m }[/math] различны. Действительно, пусть это не так, тогда существуют такие [math]\displaystyle{ i_1 \neq i_2 }[/math], что

[math]\displaystyle{ x_{i_1} a \equiv x_{i_2} a\pmod m }[/math]

или

[math]\displaystyle{ (x_{i_1} - x_{i_2}) a \equiv 0\pmod m. }[/math]

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

[math]\displaystyle{ x_{i_1} - x_{i_2} \equiv 0\pmod m }[/math] или [math]\displaystyle{ x_{i_1} \equiv x_{i_2}\pmod m }[/math].

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

Перемножим все сравнения вида [math]\displaystyle{ x_i a \equiv x_j\pmod m }[/math]. Получим:

[math]\displaystyle{ x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m }[/math]

или

[math]\displaystyle{ x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m }[/math].

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

[math]\displaystyle{ a^{\varphi(m)}-1 \equiv 0\pmod m }[/math]

или

[math]\displaystyle{ a^{\varphi(m)} \equiv 1\pmod m. }[/math] ■

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

Рассмотрим мультипликативную группу [math]\displaystyle{ \mathbb Z_n^* }[/math] обратимых элементов кольца вычетов [math]\displaystyle{ \mathbb Z_n }[/math]. Её порядок равен [math]\displaystyle{ \varphi(n) }[/math] согласно определению функции Эйлера. Поскольку число [math]\displaystyle{ a }[/math] взаимно просто с [math]\displaystyle{ n }[/math], соответствующий ему элемент [math]\displaystyle{ \overline a }[/math] в [math]\displaystyle{ \mathbb Z_n }[/math] является обратимым и принадлежит [math]\displaystyle{ \mathbb Z_n^* }[/math]. Элемент [math]\displaystyle{ \overline{a}\in \mathbb Z_n^* }[/math] порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит [math]\displaystyle{ \varphi(n) }[/math], отсюда [math]\displaystyle{ \overline a^{\varphi(n)}=\overline 1 }[/math]. ■

См. также

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

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 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  (англ.)