МОШ 2026, 11 класс, задача 5
Назовём натуральное хорошим, если найдутся такие натуральные числа , что наибольшие общие делители всевозможных пар из них образуют последовательных натуральных чисел. Существует ли хорошее натуральное число, большее ?
(А. Тертерян)
Решение. Предположим, что найдётся хорошее натуральное число . Тогда найдутся такие натуральные числа , что наибольшие общие делители всевозможных пар из них образуют последовательных натуральных чисел - обозначим их .
Заметим, что для любого натурального числа если среди чисел ровно чисел делятся на , то среди их попарных НОД-ов ровно делятся на . Далее можно рассуждать по-разному.
Первый способ.
Заметим, что при у числа найдётся по крайней мере различных простых делителя. В частности, у найдётся простой делитель , отличный от . Тогда среди чисел ровно делятся на . Однако число вида не может быть простым числом, отличным от , поскольку при у него по крайней мере два различных простых делителя, а при получаем значения . Противоречие.
Второй способ.
Поскольку попарные НОДы чисел образуют последовательных натуральных чисел, то количество чисел среди них, делящихся на , равно или .
Рассмотрим числа . Заметим, что для любого числа и отличаются не больше чем на . Действительно, поскольку для каждого выполнены неравенства
имеет место оценка
Рассмотрим такое минимальное натуральное , что . Поскольку , а , получаем, что и - два числа, большие , отличающиеся не больше чем на . С другой стороны, как было отмечено выше, оба числа и имеют вид , где - натуральное. Но при соседние числа такого вида отличаются хотя бы на , поскольку
Противоречие.