Конкурсная задача №92 (6 баллов)
Доказать, что натуральное число n является ненулевой степенью простого числа тогда и только тогда, когда n кратно n-ф(n), где ф(n) - функция Эйлера.
Решение
Пусть n = pk. Тогда ф(n) = pk-1*(p-1) и n/(n-ф(n)) = p.
Обратно, пусть n = p1k_1*…*psk_s и n = t*(n-ф(n)).
Тогда p1k_1*…*psk_s =
t*(p1k_1*…*psk_s - p1k_1-1*…*psk_s-1*(p1-1)*…*(ps-1)),
т.е. p1*…*ps = t*(p1*…*ps - (p1-1)*…*(ps-1)).
Отсюда t/(t-1) = p1/(p1-1)*…*ps/(ps-1) (*)
Пусть p1 - наибольший из простых делителей n. Тогда он не может ни с чем
сократиться и из (*) следует, что t кратно p1 и, значит,
t/(t-1) ≤ p1/(p1-1), что строго меньше правой части (*) при s > 1.
Награды
За правильное решение задачи 92 Андрей Халявин, Влад Франк, Виктор Филимоненков, Алексей Извалов и Алексей Волошин получают по 6 призовых баллов. Евгений Машеров получает 3 призовых балла, Виктор Михайлов - 1 призовой балл.
Эстетическая оценка задачи - 3 балла