Лабораторная работа № 5 Классы по данному модулю. Функция Эйлера.

По модулю существует классов сравнимых чисел.

Определение 1. Классом вычетов по данному модулю называется множество всех целых чисел, сравнимых с некоторым данным числом , и обозначается .

Число классов по модулю конечно и равно . Например, для класса =6:

Определение 2. Полной системой вычетов по данному модулю называется система чисел, взятых по одному из каждого класса по этому модулю.

Пример 1. - полная система вычетов по модулю 6.

Определение 3. Наибольшим делителем класса называется НОД любого числа из этого класса и модуля.

Определение 4. Приведенной системой вычетов по некоторому модулю называется система чисел, взятых по одному из каждого класса, взаимно простого с модулем.

Пример 2. - приведенная система чисел по модулю 6.

Определение 5. Функцией Эйлера называется число натуральных чисел, не превосходящих и взаимно простых с .

Определение 6. Функцией Эйлера называется число классов по модулю m, взаимно простых с этим модулем.

По модулю 1 имеется один класс чисел, взаимно простых с модулем, поэтому .

Пример 3. Определить . Для этого выписываем натуральные числа от 1 до 24 и оставляем среди них, взаимно простые с 24. Получим числа 1,5,7,11,13,17,19,23. равно числу этих чисел, то есть =8.

Свойства функции Эйлера:

1. , (мультипликативность).

2. Если - простое число, то .

3. Если , то

4. Если , то

Задания для самостоятельной работы.

1. Записать при помощи сравнений все классы по модулю 10.

2. По какому модулю числа 20, -4, 22, 18, -1 составляют полную систему вычетов.

3. Доказать, что система чисел 20, 31, -8, -5, 25, 14, 8, -1, 13, 6 не является полной системой вычетов по модулю 10.

4. Представить графически изменение функции .

5. Вычислить .

6. Доказать справедливость следующих равенств:

1) ; 2)

7. Решить уравнения

1)

8. Чему равна сумма