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

(a) Пусть Предположим, что существует лишь конечное множество простых чисел, которые делят хотя бы одно значение Обозначим их …, Рассмотрим произведение

Тогда для любого и потому

Значит, ни одно из простых …, не делит Следовательно, у найдётся простой делитель, отличный от …, Получили противоречие. Таким образом, простых, которые встречаются в значениях бесконечно много.

(b) Из пункта (a) мы знаем, что таких простых бесконечно много. Выберем любые различных простых …, для которых при некоторых Заметим, что для любого целого

Потребуем следующую систему сравнений:

Так как простые …, попарно различны, система имеет решение по Китайской теореме об остатках. Для такого имеем

и значит, делится как минимум на различных простых чисел.