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

Пусть a, m - натуральные числа, причем НОД(a, m)=1. Тогда a^j(m)º1 (mod m).

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

1). Для начала рассмотрим случай, когда m=pⁿ (p - простое, n - натуральное число). Тогда a^j(m)ºa^p-1*a^p-1*...*a^p-1º1 (mod m). Первый переход сделан ввиду того, что j(pⁿ)=pⁿ-p^n-1=p^n-1(p-1), второе - по малой теореме Ферма.
2). Докажем теорему Эйлера. Разложим число m на простые множители: m=p^aq^b... Тогда a^j(m)ºa^p-1*a^p-1*...*a^p-1*a^q-1*a^q-1*...*a^q-1*...º a^q-1*a^q-1*...*a^q-1*...º ...º 1 (mod m).