Решение сравнений и их приложения
жүктеу/скачать 131,78 Kb.
|
| Доказательство
а) Каждое число совокупности (1) принадлежит некоторому классу. Все числа из (1) попарно несравнимы по модулю т, то есть принадлежат различным классам по модулю m. Каждое число из (1) взаимно просто с т, то есть все эти числа принадлежат различным классам, взаимно простым с модулем m. Всего в (1) имеется k чисел, то есть столько, сколько должна содержать приведенная система вычетов по модулю m. Следовательно, совокупность чисел (1) — приведенная система вычетов по модулю т. §4. Функция Эйлера. Теоремы Эйлера и Ферма. Функция Эйлера. Обозначим через φ (т) число классов вычетов по модулю m, взаимно простых с m, то есть число элементов приведенной системы вычетов по модулю т. Функция φ (т) является числовой. Ее называют функцией Эйлера. Выберем в качестве представителей классов вычетов по модулю т числа 1, ... , т - 1, т. Тогда φ (т) — количество таких чисел, взаимно простых с т. Иными словами, φ(т) — количество положительных чисел, не превосходящих m и взаимно простых с m. Примеры. Пусть т = 9. Полная система вычетов по модулю 9 состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9. Из них взаимно просты с 9 числа 1,2,4, 5, 7, 8. Так как количество этих чисел равно 6, то φ (9) = 6. Пусть т = 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. Перейдем к вычислению функции Эйлера. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу:
|