Формула китайской теоремы об остатках
Берутся несколько делителей, которые не имеют общих делителей между собой, кроме 1. Это и есть главное условие: модули должны быть попарно взаимно простыми. Тогда система условий вида «число при делении на первый модуль дает такой-то остаток», «при делении на второй — другой остаток» и так далее обязательно имеет решение.
Более того, решение фактически одно, если рассматривать его с точностью до общего периода: все подходящие числа повторяются через одно и то же расстояние. Это расстояние равно произведению модулей. На некотором промежутке длиной, равной произведению модулей, существует ровно одно число, которое удовлетворяет всем заданным остаткам.
Доказательство китайской теоремы об остатках
Смысл доказательства обычно строится на двух идеях: существование и единственность.
Существование объясняют так. Раз модули взаимно просты, можно собрать число из частей, каждая из которых отвечает только за один остаток и не мешает остальным. То есть можно подобрать такие добавки, которые меняют остаток по одному модулю, но по другим модулям дают ноль и ничего не портят. Складывая такие части, получают число, которое выполняет сразу все условия.
Единственность доказывают через разность двух решений. Если два числа дают одинаковые остатки при делении на каждый модуль, значит их разность делится на каждый из модулей. А так как модули взаимно просты, то разность делится на их произведение.
