Количество классов вычетов в приведенной системе вычетов минус один обозначают как и называют функцией Эйлера (или представляет собой количество чисел ряда взаимно простых с ). Например, , , , , , , . Кроме того, .
Свойства функции Эйлера:
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.
Решение
, . По теореме Ферма: .
Умножим эти сравнения и вычтем : .●
Пример
Найти вычет числа по .
Решение
Разделим степень на с остатком ; . По теореме Ферма (так как – простое): .
Тогда . Значит, .●