Решение сравнений и их приложения

Теорема 2.
Пусть число классов, взаимно простых с m, равно k. Тогда любая совокупность k целых чисел
(1)
попарно несравнимых по модулю m и взаимно простых с m, пред­ставляет собой приведенную систему вычетов по модулю m.
Доказательство
а) Каждое число совокупности (1) принадлежит некоторому классу.

2. 
   Все числа из (1) попарно несравнимы по модулю т, то есть принадлежат различным классам по модулю m.
   
3. 
   Каждое число из (1) взаимно просто с т, то есть все эти числа принадлежат различным классам, взаимно простым с модулем m.
   
4. 
   Всего в (1) имеется k чисел, то есть столько, сколько должна содержать приведенная система вычетов по модулю m.
   

Следовательно, совокупность чисел (1) — приведенная система вычетов по модулю т.

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

Теоремы Эйлера и Ферма.

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

Обозначим через φ (т) число классов вы­четов по модулю m, взаимно простых с m, то есть число элементов приведенной системы вычетов по модулю т. Функция φ (т) яв­ляется числовой. Ее называют функцией Эйлера.
Выберем в качестве представителей классов вычетов по модулю т числа 1, ... , т - 1, т. Тогда φ (т) — количество таких чисел, взаимно простых с т. Иными словами, φ(т) — количество поло­жительных чисел, не превосходящих m и взаимно простых с m.
Примеры.

1. 
   Пусть т = 9. Полная система вычетов по модулю 9 состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9. Из них взаимно просты с 9 числа 1,2,4, 5, 7, 8. Так как количество этих чисел равно 6, то φ (9) = 6.
   
2. 
   Пусть т = 12. Полная система вычетов состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Из них взаимно просты с 12 числа 1, 5, 7, 11. Значит,
   

φ(12) = 4.
При т = 1 полная система вычетов состоит из одного класса 1. Общим натуральным делителем чисел 1 и 1 является 1, (1, 1) = 1. На этом основании полагают φ(1) = 1.
Перейдем к вычислению функции Эйлера.