Малая теорема Ферма

Продолжение серии "О математике и математиках"


Теперь вернемся к рассуждениям о бесполезности. Часто “бесполезные математические открытия” становятся применимы для реальных задач, но при этом не теряют прелести обобщения и красоты человеческой мысли.
Так, например, сегодня криптографию нельзя представить без теории чисел и в частности без малой теоремы Ферма. Малая теорема Ферма дала основу для создания первой системы кодирования с открытым ключом RSA.
[см. Фороузан Б.А. Криптография и безопасность сетей: Учебное пособие /. Перевод с англ. под ред. А.Н. Берлина — М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. — 784 с.: ил., табл. — (Основы информационных технологий)].
Самый общий алгоритм использования открытого ключа доступа — криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).
Система с открытым ключом заключается в том, что кодирующая последовательность открыта и может быть опубликована, а закодированный текст не может быть раскодирован посторонним лицом. Заметим, что алгоритм кодирования криптографических систем  не скрывается. Так что такое свойство в начале кажется удивительным.
 Чтобы раскрыть эту тайну рассмотрим теперь малую теорему Ферма.
 
Она формулируется следующим образом

Если p- простое число и a — целое число, не делящееся на p, то a^p-1  (a в степени p-1)делится на p, то есть a^p-1 (a в степени p-1)   при делении нацело на p даёт в остатке 1
В дальнейшем в 1780 году эта теорема была дополнена Эйлером.
В математику была введена функция Эйлера. Функция Эйлера (обозначается греческой буквой фи (n))  показывает, сколько натуральных чисел из отрезка [1,n-1]  имеют c n  только один общий делитель — единицу. Иными словами, сколько на этом отрезке числе взаимно простых с n.  Функция Эйлера определена на множестве натуральных чисел, и значения её лежат в множестве натуральных чисел.
Например: Если n=6, то фи(n)=  (1, 5)=2
Простое число p имеет p-1 взаимно простых чисел меньше p и функция фи=(p-1) .
Функция Эйлера позволила расширить область действия теоремы Ферма и сформулировать теорему:
Если фи (n)- функция Эйлера, и a  и n—взаимно просты, то

a^фи(n) (a в степени фи(n))   при делении нацело на m даёт в остатке 1.
Если n простое число, то из теоремы Эйлера сразу следует малая теорема Ферма.
Эйлер доказал, что  эта функция  является мультипликативной арифметической функцией, то есть
фи (n=ml))= фи (m) фи (l)  Если взаимно просты, т.е. (m,n)=1

 Или а^фи(ml)= [а^фи(m)]^фи(l)=1 (напомним, что в данной символике ^ операция возведения в степень).

Продолжение следует