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

) Если т = р — простое число, то φ (р) = р- 1. Доказательство

жүктеу/скачать 131,78 Kb. бет 10/14 Дата 09.06.2022 өлшемі 131,78 Kb. #36581 түрі Решение

Бұл бет үшін навигация:

• Теорема
• Примеры. № 1

1) Если т = р — простое число, то φ (р) = р- 1. Доказательство. Вычеты 1, 2, ... , р- 1 и только они взаимно просты с простым числом р. Поэтому φ(р) = р - 1. 2) Если т = рк — степень простого числа р, то φ(т) = (р - 1). (1) Доказательство. Полная система вычетов по модулю т = рк состоит из чисел 1,..., pk - 1, рк Натуральные дели­тели т являются степенями р. Поэтому число а может иметь общий делитель с m, отличный от 1, лишь в случае, когда а делится на р. Но среди чисел 1, ... , pk -1 на р делятся лишь числа р, 2р, ... , р2, ... рк, количество которых равно рк : р = рк-1. Значит, взаимно просты с т = рк остальные рк - рк-1 = pk-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) = Доказательство. Если (n,2)=1, то φ(4n)= φ(4) φ(n)=2 φ(n) Если же 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) и является искомой. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу: