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

Рассмотрим произвольную пару остатков где и По китайской теореме об остатках для взаимно простых и существует единственное число такое, что:

причём

Таким образом, для каждой пары остатков найдётся ровно одно число в промежутке от до дающее при делении на остаток а при делении на — остаток

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

Следовательно, при делении чисел от до на и на получаются все возможные пары остатков, что и требовалось доказать.