Свойства функции Эйлера
Свойство 1. Если
то
Доказательство 1. Пусть
циклическая группа порядка
число образующих ее равно
(см. утверждение 7.3.4). Так как
то допустимо разложение (см. п.7.4) группы
в прямое произведение своих циклических подгрупп
следовательно, число образующих группы
равно
Доказательство 2. Достаточно показать, что
1. Заметим, что из
следует существование целых
для которых выполняется
(алгоритм Евклида см. п. 8.1). Приведем значения целых
к значениям
для которых
Пусть
тогда верно
где значения
приведены к значениям
Таким образом, произвольное число
можно записать в виде
где а
Данное представление является однозначным, так как число возможных пар
равно
и такое же количество представляемых чисел с
Далее рассмотрим все представления
для всех
2. Пусть
т.е.
и
Покажем, что
Выражение
эквивалентно
. В первом случае —
и во втором —
Таких пар
, а значит и чисел
взаимно простых
равно
Покажем, что других чисел взаимно простых
среди
нет.
3. Остались не рассмотренными числа
где
или
для них
т.е. такие числа не являются взаимно простыми с
4. Из пунктов 1), 2), 3) следует, что
• Теорема 8.7.1 Эйлера.
где
и
Доказательство. Приведенная система вычетов
по модулю
является группой, порядок которой
Пусть
произвольное такое, что
где
Из свойств сравнений следует, что наибольший общий делитель
Теорема 7.3.1 Лагранжа утверждает, что порядок элемента группы кратен порядку этой группы. Пусть k — порядок элемента
т. е.
Отсюда
где
положительное целое. Тогда
Из
следует, что
а значит, и
Теорема 8.7.2 Ферма,
где
простое число;
произвольное целое положительное число.
Доказательство. Пусть
тогда
Пусть теперь
где
значит,
Из теоремы Эйлера следует, что
где
Отсюда
Теорема 8.7.3 Вильсона,
где
простое число.
Доказательство. Пусть
приведенная система вычетов по модулю
является группой. Для любого
существует единственный обратный элемент
такой, что
Заметим, что
выполняется только для двух элементов:
Действительно
равносильно
или
Отсюда
или
Таким образом, обратными элементами к себе являются только
Для любого из оставшихся элементов группых
существует единственный обратный
такой, что
Тогда верно
Умножив последнее сравнение на
получим
или
Задача. Пустьр — простое и
целые числа. Доказать, что