===== №92 =====
**Конкурсная задача №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 балла **
----