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

Заметим, что достаточно доказать утверждение для случая, когда — степень простого числа. Тогда для произвольного с разложением

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

Таким образом, остаётся рассмотреть случаи где — простое.

Рассмотрим сначала модуль Число взаимно просто с то есть а значит, существует обратный к по модулю Возьмём Тогда

Аналогично в модуле число обратимо, поскольку Возьмём и Тогда

Если то также и можно взять что снова даёт

Для каждого простого делителя числа мы построили пару таких что

По китайской теореме об остатках существует пара такая что

для всех и при этом