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

Системы сравнений

Рассмотрим систему из двух сравнений

$$\begin{aligned} ax & \equiv_m A \\ bx & \equiv_n B \end{aligned}$$

Без ограничения общности можно считать $a$ и $b$ равными единице:

• если $A$ делится на НОД $a$ и $m$, то всё три коэффициента сравнения можно на этот НОД сократить, получив эквивалентное сравнение
• если не делится, то сравнение не имеет решений

Пусть теперь $d=\text{НОД}(m,n)$, причём $m=dM$ и $n=dN$. То есть наша система имеет вид

$$\begin{aligned} x & \equiv_{dM} A \\ x & \equiv_{dN} B \end{aligned}$$

Решение этой системы — то же самое, что и решение системы уравнений

$$\begin{aligned} x & = dMy + A \\ x & = dNz + B \end{aligned}$$

Следствием которых является уравнение

$$d(My - Nz) = B-A$$

Если $B-A$ не делится на $d$, то это уравнение не решается, и, как следствие, исходная система сравнений не решается.

Если же $B-A$ делится на $d$, то такое уравнение решается, причём множество всех его решений имеет вид

$$\begin{aligned} y & = Y + Nk \\ z & = Z + Mk \end{aligned}$$

для какой-то пары чисел $Y$ и $Z$, удовлетворяющей

$$d(MY-NZ) = B-A$$

Более того, подстановка такого множества решений в исходную систему даёт

$$\begin{aligned} x & = dMY + A + dMNk \\ x & = dNZ + B + dMNk \end{aligned}$$

Эти два равенства, как нетрудно заметить, одинаковы, поэтому полностью множество всех решений системы имеет вид

$$\begin{aligned} x & = dMY + A + dMNk \\ y & = Y + Nk \\ z & = Z + Mk \end{aligned}$$

В итоге мы получили, что исходная система сравнений эквивалентна

$$x \equiv_{dMN} dMY + A$$

Общая теорема

Пусть $d=\text{НОД}(m,n)$, причём $m=dM$ и $n=dN$. Тогда система сравнений

$$\begin{aligned} x & \equiv_m A \\ x & \equiv_n B \end{aligned}$$

имеет решение тогда и только тогда, когда $A\equiv_d B$, причём это решение единственно по модулю $dMN$ (или, что то же самое, — по модулю $mn/d$).

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

Китайской Теоремой об Остатках (далее КТО) называется частный случай вышесформулированной теоремы для $d=1$. А именно, верно следующее.

Пусть $m$ и $n$ взаимно просты. Тогда система сравнений

$$\begin{aligned} x & \equiv_m A \\ x & \equiv_n B \end{aligned}$$

имеет единственное по модулю $mn$ решение, то есть эквивалентна одному сравнению вида

$$x \equiv_{mn} C$$