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

Теорема Эйлера в теории чисел гласит: Если 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¯.