Задача 60770

Тема:    [ Функция Эйлера ]

Сложность: 3+ Классы: 9,10,11

Условие

Известно, что  (m, n) > 1.  Что больше φ(mn) или  φ(m)φ(n)?  Определение функции φ(n) см. в задаче 60758.

Решение

Каждому простому числу p, являющемуся делителем как m, так и n, в числе φ(mn) соответствует множитель  1 – ¹/_p,  а в числе  φ(m)φ(n)  – множитель
(1 – ¹/_p)².  Так как  1 – ¹/_p < 1,  то  φ(mn) > φ(m)φ(n).

Ответ

φ(mn).

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

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