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

Теорема Эйлера гласит что, если a и n взаимно просты, то:

aφ(n) ≡ 1 mod n

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

По словию теоремы, a и n взаимно просты:

a mod n ≠ 0

По определению функции Эйлера существуют ровно φ(n) чисел взаимно простых с n. Обозначим их x1, ..., xφ(n)

Расcмотрим следующие выражения:

(a·xi) mod n для всех i от 1 до φ(n)

Так как число a взаимно простое с n по условию теоремы и xi взаимно простое с n по условию выбора x, то произведение не может быть кратным n

(a·xi) mod n ≠ 0

Следовательно, результатом (a·xi) mod n будет являться число из того же набора x (взаимно простых с n).

a·xi ≡ xj mod n

Более того, все остатки от деления разные. Если бы существовали такие i, j что:

a·xi ≡ a·xj mod n, то

a·xi - a·xj ≡ 0 mod n,

a·(xi - xj) ≡ 0 mod n,

Так как a не кратно n, то

xi - xj ≡ 0 mod n,

но это невозможно т.к. все xi разные по условию выбора x.

Получается, что произведение a·xi однозначно соответствует xj и наоборот. Любопытное свойство. Давайте теперь перемножим все эти произведения и посмотрим что получится:

x1···xφ(n)·aφ(n) ≡ x1···xφ(n) mod n,

x1···xφ(n)·(aφ(n) − 1) ≡ 0 mod n,

так как каждое x не кратно n, то их можно вычеркнуть:

aφ(n) − 1 ≡ 0 mod n,

aφ(n) ≡ 1 mod n,

что и требовалось доказать.

Частным случаем теоремы Эйлера является малая теорема Ферма