Вычисление функции Эйлера. Теорема Гаусса. Теоремы Эйлера и Ферма

Определение 14. Функцией Эйлера называется функция j(m), которая для каждого числа m Îℕ определяет количество натуральных чисел, взаимно простых с m и не превосходящих m.

Пример. Все натуральные числа, взаимно простые с m =20 и не превосходящие m: 1, 3, 7, 9, 11, 13, 17, 19. Следовательно, φ(m)=8.

Теорема 15. Пусть p - простое число, k Îℕ. Тогда φ (р^k) = р^k∙ .

Доказательство.

Расположим числа от 1 до р^k в виде таблицы:

1	2	3	…	p
р+ 1	р+ 2	р+ 3	…	p+p= 2 ∙p
2∙ р+ 1	2∙ р+ 2	2∙ р+ 3	…	2 ∙p+p= 3 ∙p
…	…	…	…	…
(рк- 1 - 1) ∙ р+ 1	(рк- 1 - 1) ∙ р+ 2	(рк- 1 - 1) ∙ р+ 3	…	(рк- 1 - 1) ∙ р+ p=рк

Из таблицы ⇒ все столбцы, кроме последнего, взаимно просты с числом p, а значит и с числом р^к . Но каждый столбец содержит р^{к- 1} чисел ⇒ в таблице (р^к- р^{к- 1}) чисел взаимно простых с числом р^к (из р^к вычтем количество элементов последнего столбца).

Таким образом, φ (р^к) =p^k . Теорема доказана.

Теорема 16. Функция Эйлера φ(m) является мультипликативной, т.е.

1) φ(1)=1;

2) если (m,n)=1, то φ(m∙n)= φ(m)∙ φ(n).

Теорема 17. Пусть m= - каноническое представление натурального числа m. Тогда φ (m) = m∙ ∙..∙ .

Доказательство.

Так как числа р _1, р_2,.., р_s взаимно просты, то в силу мультипликативности функции φ (Т.16) получаем

φ (m) = φ () = φ () ∙..∙ φ () ∙ ∙..∙ = m∙ ∙..∙ . Теорема доказана.

Теорема 18 (теорема Гаусса). Пусть m Îℕ. Тогда φ (d) =m.

Теорема 19 (теорема Эйлера). Пусть m Îℕ, m ≠ 1, a Îℤ. Если (a,m) = 1, то a^{φ ( m )} ≡ 1(mod m).

Следствие 19.1 (теорема Ферма). Пусть p – простое число, a Îℤ. Если (a,p) = 1, то a^{p- 1} ≡ 1(mod p).

Доказательство. Так как φ (p) = p- 1, то по теореме 18 ⇒ a^{p- 1} ≡ 1(mod p). Следствие доказано.

Следствие 19.2. Пусть p – простое число, a Îℤ. Тогда a^p ≡ a (mod p).

Доказательство. Возможны два случая:

1) Пусть a ∶ p ⇒ a^p : p ⇒ (a^p-a): p ⇒ a^p ≡ a (mod p);

2) Пусть a: p ⇒ (a,p) = 1. По следствию 19.1, a^{p- 1} ≡ 1(mod p). Из свойств сравнений ⇒ a^p ≡ a (mod p). Следствие доказано.