Арифметическая прогрессия

Первое решение. Назовём набор из чисел в тетради красивым, если из него получается требуемый набор наименьших общих кратных. Предположим, что красивый набор из чисел существует. Выберем из всех таких наборов набор с наименьшей суммой чисел.

Заметим, что если разность полученной прогрессии имеет общий простой делитель с каким-нибудь её членом, то все члены этой прогрессии делятся на а тогда и все числа красивого набора, за исключением, быть может, одного, также делятся на Разделим все эти числа на (кроме, возможно, того, которое не делится); все выписанные на доску числа тоже разделятся на и по-прежнему будут последовательными членами непостоянной арифметической прогрессии, то есть также получится красивый набор. Это противоречит минимальности суммы чисел выбранного набора. Следовательно, взаимно просто со всеми выписанными на доску числами.

Пусть — максимальное число нашего красивого набора; тогда В прогрессии на доске будет не менее членов, кратных У каких-то двух из них номера отличаются не более, чем на

то есть разность этих членов (также делящаяся на ) равна при некотором

Но взаимно просто с поэтому не может делиться на — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Как и в первом решении, выберем красивый набор с наименьшей суммой и докажем, что разность прогрессии взаимно проста с любым числом из набора. Далее нам понадобится следующий стандартный факт.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть разность арифметической прогрессии натуральных чисел взаимно проста с числом Тогда числа, кратные идут в этой прогрессии с периодом (то есть существует такое что члены, кратные — это в точности ).

Доказательство. Разности членов имеют вид при и они не делятся на Поэтому все эти члены дают разные остатки при делении на значит, они дают все возможные остатки, и один из наших членов делится на — пусть это Тогда член будет делиться на тогда и только тогда, когда делится на то есть когда делится на

______________________________________________________________________________________________________________________________________________________

Пусть теперь — простой делитель какого-то числа из нашего набора, а — наибольшая степень делящая число набора. Пусть — число из набора, делящееся на Хотя бы член прогрессии делится на (и, как следствие, на ). Но разность прогрессии не делится на значит, лишь каждый -й её член делится на Значит, в прогрессии хотя бы членов, то есть

откуда

С другой стороны, ни один из как минимум членов прогрессии, делящихся на не делится на Это значит, что количество таких членов меньше то есть или Это противоречит неравенству выше.