Теория чисел на ИТМО
Ошибка.
Попробуйте повторить позже
Натуральные делители натурального числа 
занумеровали по возрастанию: 
. Оказалось, что 
. Какое
наименьшее значение может принимать число 
?
Источники:
Подсказка 1
Первое, что хочется сделать, это разложить 120 на множители. Получается, что все его 16 делителей будут и делителями исходного числа. А что будет, если наше исходное число будет делится, например, на большую степень двойки?
Подсказка 2
Давайте посмотрим. Если n делится на 2^4, то к делителям n прибавится ещё 3 делителя, меньшие 120. Получается, что 120 не будет восемнадцатым делителем. Противоречие. Аналогично рассматривая 3 и 5, может ли n делится на их большие степени? Какой вывод из этого можно сделать?
Подсказка 3
Да, получаем и там аналогичное противоречие. Значит, у n есть простой делитель p, кроме 2, 3 и 5. Если мы сможем оценить его, то задача решена. Нельзя ли почти с помощью почти аналогичного противоречия получить оценку на p?
Подсказка 4
Верно, если у числа будут делители p, 2p и 3p, меньшие 120, то получается снова, что 120 минимум девятнадцатый делитель. Осталось только найти наименьший простой делитель, больший 40, посчитать ответ, и победа!
У числа 
шестнадцать делителей и все они являются делителями числа 
. Если 
делится на 
, то к этим делителям
добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.
Если 
делится на 
, то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если 
делится на 
, то к исходным
шестнадцати делителям добавляются 25,50 и 75.
Значит, 
делится на какое-то простое число 
, кроме 2,3 и 5 . Если это число не превосходит 40 , то числа 
и 
являются
делителями 
, меньшими 120 , и мы опять получаем слишком много делителей. Значит, 
хотя бы 41 , то есть 
. Заметим, что
это число нас как раз устраивает.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
