Функция Эйлера. Теоремы Эйлера и Ферма

Функция Эйлера определяется для всех натуральных чисел и представляет собой число чисел ряда 1,.., а -1, взаимно простых с а.

Найдем формулу для вычисления функции Эйлера.

Теорема.

Если - каноническое разложение числа а, то

Теорема 2.

Пусть р – простое число, , тогда

Теоремы Эйлера и Ферма являются основой всей теории сравнений и находят широкое применение как в теоретических исследованиях, так и в арифметических приложениях.

Пример.

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

Если (a,m)=1 a (I)

Доказательство: Рассмотрим мультипликационную группу классов вычетов, взаимно простых с mod m: Gm.

Эта коммутативная группа содержит элементов. Применим к ней теорему Лагранжа, вернее следствие из этой теоремы.

Порядок элемента конечной коммутативности группы G является делителем порядка этой группы, т.е. если конечная коммутативность группы состоит из элементов, то для элемента этой группы выполниться равенство:

Мы получили, что для класса выполняется равенство или (на языке сравнений)

Особенно простой вид теорема Эйлера принимает в случае, если m= p – простое число. В этом случае φ(p)= p -1, а потому получаем

Теорема Ферма. Если р - простое число, и - целое, неделящеяся на р,

то

(, p)=1, то (II)

Другая формулировка теоремы Ферма: (Следствие)

Если р – простое число, то для целого имеет место

Действительно,

а) если (а, р)=1 умножим обе части сравнения (II) на , получим

б) если (а, р)≠1, то также на р, т.е.