Теорема Эйлера. Если a и m - натуральные числа, причем a < m и НОД(a,m) = 1, то a φ(m) = 1, где φ(m) - функция Эйлера.
Доказательство.
Пусть G
– конечная (|G| = n < ∞) группа с операцией <*>
и e – ее единичный (нейтральный) элемент, . Любой элемент a О G путем возведения в целую
степень k (многократного применения групповой операции: ak = a*a*a*…*a) порождает конечную
циклическую подгруппу H группы G,
порядок которой |H| = m ≤ n, причем m – наименьшее
натуральное число, для которого am = e, а единица e О H
иначе бы H не была подгруппой. Теорема Лагранжа утверждает, что порядок
группы делится на порядок любой ее подгруппы, поскольку возможно разложение группы
по подгруппе. Следовательно n/m = k (k - натуральное) и a|G| =an = (ат)n/m =
ek = е.
Следствие.
В частном случае, мультипликативная группа Z*m
приведенной системы вычетов по модулю m, то есть чисел, меньших
m и взаимно простых с m, содержит φ(m)
элементов: |Z*m| = φ(m).
Поэтому, если число a принадлежит этой группе, то есть a < m и НОД(a,m) = 1, то a
φ(m) = 1.