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

1) Если т = р — простое число, то φ (р) = р- 1.
Доказательство.
Вычеты 1, 2, ... , р- 1 и только они взаимно просты с простым числом р. Поэтому φ(р) = р - 1.
2) Если т = р^к — степень простого числа р, то
φ(т) = (р - 1). (1)
Доказательство.
Полная система вычетов по модулю т = р^к состоит из чисел 1,..., p^k - 1, р^к Натуральные дели­тели т являются степенями р. Поэтому число а может иметь общий делитель с m, отличный от 1, лишь в случае, когда а делится на р. Но среди чисел 1, ... , p^k -1 на р делятся лишь числа р, 2р, ... , р², ... р^к, количество которых равно р^к : р = р^к-1. Значит, взаимно просты с т = р^к остальные р^к - р^к-1 = p^k-l(p-1) чисел. Тем самым доказано, что
φ (р^к) = р^к-1 (р-1).
Теорема 1.
Функция Эйлера мультипликативна, то есть для взаимно простых чисел m иn имеем φ (mn) = φ(m) φ (n).
Доказательство.
Первое требование в определении мультипликативной функции выполняется тривиальным образом: функция Эйлера определена для всех натуральных чисел, причем φ (1) = 1. Нам надо лишь показать, что если тип взаимно про­стые числа, то
φ (тп) = φ (т) φ (п). (2)
Расположим полную систему вычетов по модулю тп в виде п х т — матрицы
1 2 т
т + 1 т + 2 2т
………………………………
(п -1) т+1 (п - 1) m + 2 пт
Поскольку т и п взаимно просты, то число х взаимно просто с тп тогда и только тогда, когда х взаимно просто с т и х взаимно просто с п. Но число km + t взаимно просто с т в том и только том случае, когда t взаимно просто с т. Поэтому числа, взаимно простые с m, располагаются в тех столбцах, для которых t пробегает приведенную систему выче­тов по модулю т. Число таких столбцов равно φ (т). В каждом столбце представлена полная система вычетов по модулю п. Из этих вычетов φ (п) взаимно просты с п. Зна­чит, общее количество чисел, взаимно простых и с т и с n, равно φ (т) φ (n)
(φ (т) столбцов, в каждом из которых берется φ (п) чи­сел). Эти числа, и только они, взаимно просты с тп. Тем самым доказано, что
φ (тп) = φ (т) φ (п).
Примеры.
№1. Доказать справедливость следующих равенств
φ(4n) =
Доказательство.

1. 
   Если (n,2)=1, то φ(4n)= φ(4) φ(n)=2 φ(n)
   
2. 
   Если же n=
   

№2. Решить уравнение
Решение: так как (m)= , то = , то есть =600, =75, =3· , тогда х-1=1, х=2,
y-1=2, y=3
Ответ: х=2, y=3
Мы можем вычислить значение функции Эйлера (m), зная каноническое представление числа m:
m= .
В силу мультипликативности (m) имеем:
(m)= .
Но по формуле (1) получаем, что
-1), и поэтому
(3)
Равенство (3) можно переписать в виде:

Поскольку =m, то (4)
Формула (3) или, что то же самое, (4) и является искомой.