Теорема Эйлера. Если 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.