Русская Википедия:Теорема Эйлера (теория чисел)
Теоре́ма Э́йлера в теории чисел гласит: Шаблон:Рамка Если <math>a</math> и <math>m</math> взаимно просты, то <math>a^{\varphi(m)} \equiv 1 \pmod m</math>, где <math>\varphi(m)</math> — функция Эйлера. Шаблон:Конец рамки
Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма: Шаблон:Рамка Если <math>a</math> не делится на простое число <math>p</math>, то <math>a^{p-1} \equiv 1 \pmod p</math>. Шаблон:Конец рамки
В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю <math>m</math>.
Доказательства
С помощью теории чисел
Пусть <math>x_1, \dots, x_{\varphi(m)}</math> — все различные натуральные числа, меньшие <math>m</math> и взаимно простые с ним.
Рассмотрим все возможные произведения <math>x_i a</math> для всех <math>i</math> от <math>1</math> до <math>\varphi(m)</math>.
Поскольку <math>a</math> взаимно просто с <math>m</math>, и <math>x_i</math> взаимно просто с <math>m</math>, то и <math>x_i a</math> также взаимно просто с <math>m</math>, то есть <math>x_i a \equiv x_j\pmod m</math> для некоторого <math>j</math>.
Отметим, что все остатки <math>x_i a</math> при делении на <math>m</math> различны. Действительно, пусть это не так, тогда существуют такие <math>i_1 \neq i_2</math>, что
- <math>x_{i_1} a \equiv x_{i_2} a\pmod m</math>
или
- <math>(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.</math>
Так как <math>a</math> взаимно просто с <math>m</math>, то последнее равенство равносильно тому, что
- <math>x_{i_1} - x_{i_2} \equiv 0\pmod m</math> или <math>x_{i_1} \equiv x_{i_2}\pmod m</math>.
Это противоречит тому, что числа <math>x_1, \dots, x_{\varphi(m)}</math> попарно различны по модулю <math>m</math>.
Перемножим все сравнения вида <math>x_i a \equiv x_j\pmod m</math>. Получим:
- <math>x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m</math>
или
- <math>x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m</math>.
Так как число <math>x_1 \cdots x_{\varphi(m)}</math> взаимно просто с <math>m</math>, то последнее сравнение равносильно тому, что
- <math>a^{\varphi(m)}-1 \equiv 0\pmod m</math>
или
- <math>a^{\varphi(m)} \equiv 1\pmod m.</math> Шаблон:ЧТД
С помощью теории групп
Рассмотрим мультипликативную группу <math>\mathbb Z_n^*</math> обратимых элементов кольца вычетов <math>\mathbb Z_n</math>. Её порядок равен <math>\varphi(n)</math> согласно определению функции Эйлера. Поскольку число <math>a</math> взаимно просто с <math>n</math>, соответствующий ему элемент <math>\overline a</math> в <math>\mathbb Z_n</math> является обратимым и принадлежит <math>\mathbb Z_n^*</math>. Элемент <math>\overline{a}\in \mathbb Z_n^*</math> порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит <math>\varphi(n)</math>, отсюда <math>\overline a^{\varphi(n)}=\overline 1</math>. Шаблон:ЧТД
См. также
Литература
Ссылки
- Topics: Euler’s Theorem, Chinese Remainder Theorem, Amir Kamil, CS70, Fall 2003. UC Berkeley Шаблон:Ref-en
- RSA and the Chinese remainder theorem / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley Шаблон:Ref-en
