Функция Эйлера и теорема Эйлера из ТЧ
Ошибка.
Попробуйте повторить позже
Дано нечетное натуральное число 
Докажите, что при некотором натуральном 
у числа 
не меньше 
различных
простых делителей.
Подсказка 1
Для данного m можно определить последовательность чисел, задаваемую выражением из условия для n-го члена. Тогда наша задача - найти в этой последовательности подходящее число. Попробуем зафиксировать какое-нибудь n. Как по нему построить такое k, чтобы k-ый член последовательности был больше n-го, и простых делителей у этого члена было не меньше, чем у n-го?
Подсказка 2
Точно! Возьмем n, взаимно простое с m, а после этого положим k равным сумме n и произведения m на функцию Эйлера от квадрата n-го члена. На что делится разность k-го члена и n-го члена?
Подсказка 3
Верно, на квадрат n-го члена! Что можно сказать о простых числах, входящих в n-ый и k-ый члены?
Подсказка 4
Конечно! Все простые делители n-го члена входят в k-ый член в тех же степенях. А можно ли сравнить k-ый и n-ый члены?
Подсказка 5
Правильно! k-ый член больше! Следовательно, у него больше простых делителей, чем у n-го. А как заработать число с еще большим числом делителей?
Пусть 
Пусть 
взаимно просто с 
тогда 
взаимно просто с 
Рассмотрим число 
Тогда 
взаимно просто с 
Заметим, что 
кратно 
по теореме Эйлера, а 
кратно 
, поскольку 
делится на 
.
Следовательно, 
делится на 
. Значит, все простые делители числа 
входят в 
в тех же степенях, что и в само 
при
этом число 
больше; следовательно, у него есть другой простой делитель. Итого, по числу 
мы получили 
у которого количество
различных простых делителей больше. Теперь рассмотрим 
тогда 
взаимно просто с 
и у числа 
есть некоторые простые
делители. Производя аналогичную процедуру, за 
шагов мы получим число 
у которого не менее 
различных простых
делителей.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
