Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№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 балла


 

 


Страница: [[marathon:problem_92]]

marathon/problem_92.txt · Последние изменения: 2018/02/28 18:26 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006