Назовём натуральное плохим, если не делится на Наша цель — доказать, что плохих чисел бесконечно много.

Первое решение. Докажем, что при любом чётном одно из чисел и плохое; из этого, очевидно, следует требуемое. Предположим противное. Тогда и Иначе говоря, и Но отсюда следует, что это невозможно, ибо Противоречие.

Второе решение. При утверждение задачи очевидно, поэтому будем считать, что

Лемма. Пусть и — натуральные числа. Предположим, что делится на Тогда делится на

Доказательство. Пусть — остаток от деления на Тогда

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

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

Третье решение. Мы опять же исследуем лишь случай

Пусть — некоторый простой делитель числа Положим тогда при любом имеем то есть делится на

С другой стороны, покажем, что числа и не могут одновременно делиться на Действительно, иначе на делилась бы и их разность но это невозможно, ибо по малой теореме Ферма, а числа и взаимно просты с

Итак, либо не делится на (и, значит, на ), либо не делится на (и, значит, на ). Поэтому среди чисел бесконечно много плохих.