Билет №20. Арифметические приложения теории сравнений

Определение 10.1. Функцией Эйлера называется функция : N ® N, где (m) (m N) равно количеству взаимно простых с m натуральных чисел, не превосходящих m.

Иначе, (m) (m N) есть количество натуральных чисел k, удовлетворяющих условиям:

1 k m, (k, m) = 1.

Примеры. (1) = 1. Среди чисел 1, 2, 3, 4, 5, 6, 7, 8 взаимно простыми с 8 являются лишь 1, 5, 7. Поэтому (8) = 3.

Замечание. Функция Эйлера мультипликативна, т.е. для любых двух натуральных взаимно простых чисел а и b имеем (a∙b) = (a) ∙ (b).

Например, (6) = (2∙3) = (2) ∙ (3) = 1 ∙ 2 = 2.

Свойства функции Эйлера описываются следующей теоремой.

Теорема 10.1. Если p – простое, то

1) (p) = p – 1; 2) (p ) = p ^-1 (p – 1).

3) Для любого натурального m 2 выполняется равенство

(m) = m ∙

Иначе, если m = , то (m) = m ∙ .

Доказательство. 1) Для каждого простого числа p лишь одно из чисел среди 1, 2, …, p не взаимно просто с p, а именно само число p. Поэтому (p) = p – 1.

2) Если m = p есть степень простого числа, то нетривиальный общий делитель с m могут иметь лишь числа, делящиеся на p, т.е. числа вида pk. Неравенство 1 pk p выполняется лишь для натуральных чисел k p ^-1 и только для них. Поэтому

(p ) = p – p ^-1.

3) Пусть m = . В силу мультипликативности функции Эйлера имеем: (m) = ∙ ∙ … ∙ = ∙ (p₁ - 1) ∙ ∙ ∙ (p₂ - 1) ∙ … ∙ ∙ (p_n - 1) = m ∙ .

Примеры. Вычислить:

1) (7). 7 – простое число, поэтому (7) = 7 – 1 = 6.

2) (125). 125 = 5³, потому (125) = (5³) = 5^3-1∙(5 – 1) = 100.

3) (84). Найдем каноническое разложение 84. 84 = 2² ∙ 3 ∙ 7.

(84) = (2² ∙ 3 ∙ 7) = 84 ∙ = 24.