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

Первое решение.

По малой теореме Ферма и

Теперь взглянем на исходное выражение по модулю

Теперь взглянем на исходное выражение по модулю

Итак, и . По Китайской теореме об остатках решение такой системы сравнений по модулю, равном произведению модулей, существует и единственно, легко находим, что это

Второе решение.

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

Докажем это утверждение индукцией по (для делимость очевидна, для отрицательных доказывается аналогично или сводится к случаю положительного заменой . Если , утверждение уже проверено. Предположим теперь, что мы уже доказали, что делится на и докажем, что также делится на Посмотрим на разность этих двух выражений:

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