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

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

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