Теорема Эйлера (теория чисел)
Теоре́ма Э́йлера в теории чисел гласит:
Если [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 (англ.)
Для улучшения этой статьи желательно: |