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

Пойдём от противного, пусть делит Для каждого посчитаем НОД и рассмотрим такое у которого получился наибольший НОД. Пусть полученный НОД равен (). По условию делится на однако не может делиться на значит делит Но по условию и делится на а значит, что также делится на Аналогичными рассуждениями получаем, что все при делятся на Далее с помощью предположения, что делится на понимаем, что кратно Следовательно, делит и поскольку кратно Далее, продолжая цепочку рассуждений, приходим к выводу, что все от при также кратны Поскольку — наибольший НОД среди всех вида получаем, что для любого

Пусть По условию кратно а значит необходимо, чтобы В силу произвольности получаем, что при всех от до

Заметим, что и взаимно просты, в противном случае пусть их НОД равен Выше мы доказали, что кратно а кратно и получается, что оба числа кратны Тогда также должно делиться на противоречие.

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