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

Рассмотрим произвольное число из набора. Попробуем подобрать для такой остаток по модулю чтобы никогда не входило в Понятно, что иначе при условие нарушится. Числа суммарно дают не более остатка при делении на Таким образом мы поняли, что числа имеют не более различных остатков по модулю Нетрудно понять, что потому что не меньше -го простого числа из натурального ряда, которое, в свою очередь, больше Но тогда существует такой остаток который не встречается среди остатков чисел при делении Таким образом, можно взять Осталось заметить, что по КТО существует такое что при что и требовалось.