WikiSort.ru - Не сортированное

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

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

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

Поскольку ${\displaystyle a}$ взаимно просто с ${\displaystyle m}$ и ${\displaystyle x_{i}}$ взаимно просто с ${\displaystyle m}$ , то и ${\displaystyle x_{i}a}$ также взаимно просто с ${\displaystyle m}$ , то есть ${\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}}$ для некоторого ${\displaystyle j}$ .

Отметим, что все остатки ${\displaystyle x_{i}a}$ при делении на ${\displaystyle m}$ различны. Действительно, пусть это не так, тогда существуют такие ${\displaystyle i_{1}\neq i_{2}}$ , что

${\displaystyle x_{i_{1}}a\equiv x_{i_{2}}a{\pmod {m}}}$

или

${\displaystyle (x_{i_{1}}-x_{i_{2}})a\equiv 0{\pmod {m}}.}$

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

${\displaystyle x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}}$ или ${\displaystyle x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}}$ .

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

Перемножим все сравнения вида ${\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}}$ . Получим:

${\displaystyle x_{1}\cdots x_{\varphi (m)}a^{\varphi (m)}\equiv x_{1}\cdots x_{\varphi (m)}{\pmod {m}}}$

или

${\displaystyle x_{1}\cdots x_{\varphi (m)}(a^{\varphi (m)}-1)\equiv 0{\pmod {m}}}$ .

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

${\displaystyle a^{\varphi (m)}-1\equiv 0{\pmod {m}}}$

или

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}.}$ ■

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

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