М23. Доказательство теоремы Ферма-Эйлера

Полезно будет начать с доказательства малой теоремы Ферма; в этом случае обобщение на случай теоремы Ферма-Эйлера остановится почти очевидным.

Малая теорема Ферма утверждает, что

Если p - простое число, то для любого целого числа M, которое не делится на p, справедливо

M^(p-1)1(mod p).

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

Полное множество вычетов ("остатков") по модулю p для чисел, которые не делятся на p, есть

1, 2, 3, ..., (p-1).

Умножим каждое из этих чисел на M:

M, 2M, 3M, ..., (p-1)M.

Никакая пара из этого множества чисел не дает по модулю p одного и того же вычета, так как если бы, например, выполнялось

aM  bM(mod p),

то в этом случае число M(a-b) делилось бы на p. Однако M не делится на p, а числа a и b оба меньше p. Поэтому все (p-1) этих чисел будет различны по модулю p. Следовательно, это то же самое множество чисел

1, 2, 3, ..., (p-1),

только переставленное в некотором порядке. Поэтому

M2M3M...((p-1)M)  123...(p-1)(mod p)=(p-1)!(mod p).

Поскольку число (p-1)! не имеет общих делителей с p, то его можно исключить из обеих частей последнего сравнения, после чего получаем:

M^(p-1)1(mod p),

что и доказывает Малую теорему Ферма.

Доказательство теоремы Ферма-Эйлера

Теперь мы имеем дело с составным модулем N. Доказательство выполняется аналогично предыдущему, но теперь вместо использования всех вычетов по модулю p мы должны рассмотреть только те из них, которые не имеют с N общих делителей. Если обозначить их через

a₁, a₂,..., a_k,

где k=(N), а (N) - это функция Эйлера, определенная в М11. Если каждый из этих вычетов умножить на M, то они, как и ранее, все останутся различными, так как если бы выполнялось

Ma_r  Ma_s (mod N),

то M(a_r-a_s) делилось бы на N. Но это невозможно, так как M не имеет с N общих делителей, а (a_r-a_s) меньше N. Итак, мы доказали, что

если M не имеет с N общих делителей, то

M^(N)1(mod N),

и теорема Ферма-Эйлера доказана.

В системе шифрования RSA нам понадобится только частный случай, когда N=pq, где p и q - два различных простых числа. В этом случае (N)=(p-1)(q-1).