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

Теорема Эйлера в теории чисел гласит: Если a и m взаимно просты, то aφ(m)1(modm), где φ(m) — функция Эйлера.
 Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма: Если a не делится на простое число p, то ap11(modp).
 В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю m.

Доказательства


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


 Пусть x1,,xφ(m) — все различные натуральные числа, меньшие m и взаимно простые с ним.
 Рассмотрим все возможные произведения xia для всех i от 1 до φ(m).
 Поскольку a взаимно просто с m и xi взаимно просто с m, то и xia также взаимно просто с m, то есть xiaxj(modm) для некоторого j.
 Отметим, что все остатки xia при делении на m различны. Действительно, пусть это не так, тогда существуют такие i1i2, что

xi1axi2a(modm)
  или

(xi1xi2)a0(modm).
  Так как a взаимно просто с m, то последнее равенство равносильно тому, что

xi1xi20(modm) или xi1xi2(modm).
  Это противоречит тому, что числа x1,,xφ(m) попарно различны по модулю m.
 Перемножим все сравнения вида xiaxj(modm). Получим:

x1xφ(m)aφ(m)x1xφ(m)(modm)
  или

x1xφ(m)(aφ(m)1)0(modm).
  Так как число x1xφ(m) взаимно просто с m, то последнее сравнение равносильно тому, что

aφ(m)10(modm)
  или
aφ(m)1(modm).

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


 Рассмотрим мультипликативную группу Zn обратимых элементов кольца вычетов Zn. Её порядок равен φ(n) согласно определению функции Эйлера. Поскольку число a взаимно просто с n, соответствующий ему элемент a¯ в Zn является обратимым и принадлежит Zn. Элемент a¯Zn порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит φ(n), отсюда a¯φ(n)=1¯.