Теорема Эйлера

Определение:
Функция Эйлера $\varphi(m)$ —это количество натуральных чисел, меньших $m$, взаимно простых с $m$.

Утверждение: (Теорема Эйлера)
Пусть $a$ взаимно просто с $m$. Тогда $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Доказательство:
Пусть $x_1, x_2, \ldots, x_{\varphi(m)}$ — все натуральные числа, меньшие $m$ и взаимно простые с $m$. Рассмотрим следующий набор чисел: $ax_1, ax_2, \ldots, ax_{\varphi(m)}$ (все числа рассматриваются по модулю $m$). Число $a$ обратимо по модулю $m$, так как взаимно просто с ним. Из этого следует, что для $i \neq j$: $ax_i \neq ax_j$. Также заметим, что все эти числа обратимы по модулю $m$ как произведение двух обратимых (каждое из $x_i$ также обратимо по модулю $m$, так как взаимно просто с ним). Следовательно, множество чисел $x_1, x_2, \ldots, x_{\varphi(m)}$ совпадает с множеством чисел $ax_1, ax_2, \ldots, ax_{\varphi(m)}$. Значит $x_1 x_2 \ldots x_{\varphi(m)} \equiv a^{\varphi(m)} x_1 x_2 \ldots x_{\varphi(m)} \pmod{m}$. Осталось заметить, что произведение $x_1 x_2 \ldots x_{\varphi(m)}$ также обратимо, из чего получаем $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Автор конспекта: Даниил Николенко

По всем вопросам пишите в telegram @qoo2p5