Задача 60777

Темы:    [ Функция Эйлера ] [ НОД и НОК. Взаимная простота ]

Сложность: 4- Классы: 10,11

Условие

Докажите равенства:
  а)  φ(m) φ(n) = φ((m, n)) φ([m, n]);
  б)  φ(mn) φ((m, n)) = φ(m) φ(n) (m, n).
Определение функции φ(n) см. в задаче 60758.

Решение

  Из мультипликативности функции Эйлера следует, что формулу достаточно доказать в случае, когда числа m и n суть степени одного и того же простого числа. Пусть
m = p^α,  n = p^β  (α ≥ β ≥ 0.

а) Нужное тождество следует из равенств  [m, n] = m = p^α,  (m, n) = n = p^β.

  б) Задача сводится к проверке равенства  φ(p^α+β)φ(p^β) = φ(p^α)φ(p^β) p^β.
  Оно, в свою очередь, следует из соотношения  φ(p^α) = p^α–1(p – 1)  (см. задачу  60758).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.151