Как доказать теорему Эйлера?

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

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

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

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

{/displaystyle x_{i_{1}}a/equiv x_{i_{2}}a{/pmod {m}}} x_{i_1} a / equiv x_{i_2} a/pmod m

или

{/displaystyle (x_{i_{1}}-x_{i_{2}}) a/equiv 0{/pmod {m}}.} (x_{i_1} - x_{i_2}) a / equiv 0/pmod m.

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

{/displaystyle x_{i_{1}}-x_{i_{2}}/equiv 0{/pmod {m}}} x_{i_1} - x_{i_2} / equiv 0/pmod m или {/displaystyle x_{i_{1}}/equiv x_{i_{2}}{/pmod {m}}} x_{i_1} / equiv x_{i_2}/pmod m.

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

Перемножим все сравнения вида {/displaystyle x_{i}a/equiv x_{j}{/pmod {m}}} 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}}} 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}}} x_1 / cdots x_{/varphi (m) } (a^{/varphi (m) }-1) / equiv 0/pmod m.

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

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