Из мультипликативности функции Эйлера следует, что формулу достаточно доказать в случае, когда числа 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)  (см. задачу  160758).

Ответ задачи отсутствует