Теоремы Эйлера и Ферма

Теорема 1: При m > 1 и (а, m) = 1 имеем (теорема Эйлера):

.

Доказательство: Если x пробегает приведенную систему вычетов

x = r₁, r₂, …, r_c; c=j(m),

составленную из наименьших неотрицательных вычетов, то наименьшие неотрицательные вычеты r₁, r₂, ...., r_c чисел ах будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (п.

Перемножая почленно сравнения

ar₁ º r₁(mod m), ar₂ º r₂(mod m), …, ar_c º r_c(mod m),

получим

a^cr₁r_2…r_c º r₁r₂…r_c(mod m),

откуда, деля обе части на произведение r₁r_2…r_c º r₁r₂…r_c, получим

a^c º 1(mod m).

Теорема 2: При p простом и а, не делящемся на p, имеем (теорема Ферма):

, (1)

Эта теорема является следствием теоремы (Теорема 1) при m = р. Последней теореме можно придать более удобную форму. Именно, умножая обе части сравнения (1) на а, получим сравнение

a^p º a(mod p),

справедливое уже при всех целых а, так как оно верно и при а, кратном р.

Глава 4