Теорема Эйлера: различия между версиями
Nikolenko (обсуждение | вклад) |
Nikolenko (обсуждение | вклад) |
||
Строка 11: | Строка 11: | ||
|Показать название=1 | |Показать название=1 | ||
|Утверждение=Пусть $a$ взаимно просто с $m$. Тогда $a^{\varphi(m)} \equiv 1 \pmod{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)}$ — все натуральные числа, меньшие $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}$. |
}} | }} | ||
Текущая версия на 06:36, 16 сентября 2019
Теорема Эйлера
Определение:
Функция Эйлера $\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