Китайская теорема об остатках

Способ 1

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

Осталось заметить, что, с какого бы из первых четырёх чисел мы ни начали, через четыре шага мы придём к этому же числу(так как по одному разу прибавим и и по одному разу вычтем). Следовательно, в нашем ряду обязательно найдутся два одинаковых числа.

Способ 2

Пусть — наименьшее простое число в этом ряду большее По китайской теореме об остатках существует такое число (), что

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

Способ 3

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

количество простых меньше Из этого будет следовать, что в ряду обязательно найдутся равные числа. Пусть — количество чисел в этом ряду, кратных Подсчитаем количество чисел в ряду (*), кратных и По формуле включений-исключений это количество равно

Если то на делится каждое -ое число в ряду (*) и или Следовательно,

Итого, в ряду (*) не менее чисел, кратных и Из этих чисел не более трёх являются простыми — это сами числа и если они там есть. Поэтому в ряду (*) не более простых.