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

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

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

\[ \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\)).