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

 

Количество классов вычетов в приведенной системе вычетов минус один обозначают как и называют функцией Эйлера (или представляет собой количество чисел ряда взаимно простых с ). Например, , , , , , , . Кроме того, .

 

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

1. Если – простое, то .

2. Если – простое, то .

3. Мультипликативность функции Эйлера: если .

Следствие из этого свойства: .

Пример

Дано . Найдем простые все числа , на которые делится без остатка: 3, 5. Тогда . Посчитаем для проверки количество классов в приведенной системе вычетов: 1, 2, 4, 7, 8, 11, 13, 14. Оно равно 8. ●

 

Теорема 4.2 (Теорема Эйлера)

Пусть , , – функция Эйлера. Тогда: .

Например, , .

 

Теорема 4.3 (Малая теорема Ферма)

Если , – простое, то

Следствие из теоремы Ферма: , где не обязательно , но – простое.

 

Пример

Девятая степень однозначного числа оканчивается цифрой . Найти это число.

 

Решение

. Понятно, что , , .

По теореме Эйлера: , возведем в квадрат обе части сравнения: . Почленно поделим на : . ●

Пример

Доказать, что .

 

Решение

. – простое. По теореме Ферма: , где . Получаем систем:

Возводим каждое сравнение почленно в третью степень и складываем: .●

 

Пример

Найти остаток от деления на .

Решение

– простое, по теореме Ферма . Возведем данное сравнение в 4-ую степень и умножим на : остаток равен .●

 

Пример

Найти две последние цифры числа .

Решение

Две последние цифры числа – это остаток от деления на 100.

, значит:

. Так как , по теореме Эйлера . , 2 и 5 простые числа, значит: . Тогда: ; возведем в 10 степень и умножим на : .

Значит, последние две цифры 4 и 9. ●

 

Пример

Показать, что делится на 105.

Решение

, . По теореме Ферма: .

Умножим эти сравнения и вычтем : .●

 

Пример

Найти вычет числа по .

 

Решение

Разделим степень на с остатком ; . По теореме Ферма (так как – простое): .

Тогда . Значит, .●