8.7. Функция Эйлера

• Определение. Функция Эйлера определяется для всех целых положительных и равна количеству чисел ряда

взаимно простых где число 1 полагается взаимно простым с любым из чисел и

Примеры.

Замечание. Отметим, что порядок группы приведенной системы вычетов по модулю равен

Свойства функции Эйлера

Свойство 1. Если то

Доказательство 1. Пусть циклическая группа порядка число образующих ее равно (см. утверждение 7.3.4). Так как то допустимо разложение (см. п.7.4) группы в прямое произведение своих циклических подгрупп следовательно, число образующих группы равно

Доказательство 2. Достаточно показать, что

1. Заметим, что из следует существование целых для которых выполняется (алгоритм Евклида см. п. 8.1). Приведем значения целых к значениям для которых Пусть тогда верно где значения приведены к значениям Таким образом, произвольное число можно записать в виде где а Данное представление является однозначным, так как число возможных пар равно и такое же количество представляемых чисел с Далее рассмотрим все представления для всех

2. Пусть т.е. и Покажем, что Выражение эквивалентно . В первом случае — и во втором — Таких пар , а значит и чисел взаимно простых равно Покажем, что других чисел взаимно простых среди нет.

3. Остались не рассмотренными числа где или для них т.е. такие числа не являются взаимно простыми с

4. Из пунктов 1), 2), 3) следует, что

Свойство где простое число и

Доказательство. Числа вида к где это все числа не взаимно простые среди а значит остальные являются взаимно простыми Отсюда

Свойство 3. Пусть разложение числа на простые сомножители имеет вид где простые числа, тогда

Свойство где различные делители числа

Доказательство 1. Пусть разложение числа на простые сомножители. Правило обобщенного произведения (см. п.3.4) позволяет записать:

Сумма

Отсюда искомая сумма

Доказательство 2. Пусть циклическая группа порядка Для всякого делителя числа существует единственная подгруппа порядка Образующие группы составляют множество Из утверждения 7.3.4 следует, что число образующих группы равно Так как для то или

• Теорема 8.7.1 Эйлера. где и Доказательство. Приведенная система вычетов по модулю является группой, порядок которой Пусть произвольное такое, что где Из свойств сравнений следует, что наибольший общий делитель Теорема 7.3.1 Лагранжа утверждает, что порядок элемента группы кратен порядку этой группы. Пусть k — порядок элемента т. е. Отсюда где положительное целое. Тогда Из следует, что а значит, и

Теорема 8.7.2 Ферма, где простое число; произвольное целое положительное число.

Доказательство. Пусть тогда Пусть теперь где значит, Из теоремы Эйлера следует, что где Отсюда

Теорема 8.7.3 Вильсона, где простое число.

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

Заметим, что выполняется только для двух элементов: Действительно равносильно или Отсюда или Таким образом, обратными элементами к себе являются только

Для любого из оставшихся элементов группых существует единственный обратный такой, что Тогда верно Умножив последнее сравнение на получим или

Задача. Пустьр — простое и целые числа. Доказать, что

Решение. Согласно теореме Ферма

Свойства операции сравнения (см. п. 8.4) позволяют записать данные сравнений в виде их суммы: . С другой стороны, верно и что непосредственно вытекает из теоремы Ферма.