3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.

В этом пункте будут доказаны важнейшие теоремы теории чисел и показаны их приложения к задачам криптографии.

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

При m > 1, (a, m) = 1 a^φ(m) ≡ 1 (mod m).

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

Если x пробегает приведенную систему вычетов x = r₁, r₂,…,r_c (c = φ(m)), составленную из наименьших неотрицательных вычетов, то в силу того, что (a,m)=1, наименьшие неотрицательные вычеты чисел ax = ρ₁, ρ₂,…, ρ_c будут пробегать ту же систему, но, возможно, в другом порядке (это следует из утверждения 2 пункт 3). Тогда, очевидно,

r₁·…·r_c = ρ₁·… ·ρ_c *

Кроме того, справедливы сравнения

ar₁ ≡ ρ₁(mod m), ar₂ ≡ ρ₂(mod m), … , ar_c ≡ ρ_c(mod m).

Перемножая данные сравнения почленно, получим

a^c ·r₁ ·r₂ ·…·r_c ≡ ρ ₁·…· ρ _c(mod m)

Откуда в силу (*) получаем

a^c ≡ 1 (mod m)

А поскольку количество чисел в приведенной системе вычетов по модулю m есть φ(m), то есть c = φ(m), то

a^φ(m) ≡ 1 (mod m).

□

Теорема Ферма (малая)

р – простое, p не делит a a^p–1 ≡ 1 (mod m)

Доказательство: по теореме Эйлера при m=p.

Важное следствие:

a^p ≡ a (mod p) a, в том числе и для случая p\a.

Теорема Эйлера применяется для понижения степени в модулярных вычислениях.

Пример:

10¹⁰⁰ mod 11 = 10^9∙11+1 = 10⁹⁺¹ mod 11 = (–1)¹⁰ mod 11 = 1.

Следствие:

Если a: 0 < a < p, для которого a^p–1 1 (mod p) p – составное.

Отсюда –