Если \(m\) \(-\) простое число и \(a\) \(-\) взаимно простое число к \(m\), тогда \(a^{m - 1} \equiv 1 \pmod m\).

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

Рассмотрим числа \(a, \text{ } 2a, \text{ } 3a, \ldots, \text{ } ma\). Никакие два из этих чисел не дают при делении на \(m\) одинаковых остатков. Поэтому при делении на \(m\) числа \(a, \text{ } 2a, \text{ } 3a, \ldots, \text{ } ma\) дают остатки \(0, 1, 2, \ldots, m - 1\) в каком-то порядке, где 0 получается при делении \(ma \text{ на } m\). Опуская 0, имеем \(a^{m - 1} (m - 1)! \equiv (m - 1)! \pmod m)\). Вычитая правую часть равенства из левой, получаем \(a^{m - 1} (m - 1)! - (m - 1)! \equiv 0 \pmod m\), откуда следует, что \( (a^{m - 1} - 1)(m - 1)! \) делится на \(m\). Так как \(m\) не делит \((m - 1)!\) и является простым числом, то \(m\) делит \(a^{m - 1} - 1\).