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

Китайская теорема об остатках формулируется следующим образом:

Теорема.

Пусть $p_1, p_2, \ldots, p_k$ - попарно взаимно простые числа, большие 1, и пусть $P = p_1 \cdot p_2 \cdot \ldots \cdot p_k$. Тогда существует единственное неотрицательное решение по модулю $P$ следующей системы сравнений:

$x \equiv a_1 \pmod{p_1}$,

$x \equiv a_2 \pmod{p_2}$, (*)

$\ldots$,

$x \equiv a_k \pmod{p_k}$.

Другими словами, отображение, которое каждому целому числу $x$, $0\le x <P$, ставит в соответствие кортеж $a_1, a_2, \ldots, a_k$, где $x \equiv a_i \pmod{p_i}, i = 1, \ldots k$ является биекцией кольца $Z_P$ на декартово произведение $Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}$ колец $Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}$.

Т.е. соответствие между числами и кортежами является взаимно однозначным, кроме того, операции, выполняемые над числом $a$, можно эквивалентно выполнять над соответствующими элементами кортежами путём независимого выполнения операций над каждым компонентом:

если

$a \Longleftrightarrow (a_1, \ldots, a_k)$,

$b \Longleftrightarrow (b_1, \ldots, b_k)$,

то справедливо:

$(a+b) \pmod{p} \Longleftrightarrow ( (a_1+b_1) \pmod{p_1}, (a_2+b_2) \pmod{p_2}, \ldots, (a_k+b_k) \pmod{p_k})$,

$(a-b) \pmod{p} \Longleftrightarrow ( (a_1-b_1) \pmod{p_1}, (a_2-b_2) \pmod{p_2}, \ldots, (a_k-b_k) \pmod{p_k})$,

$(a\cdot b) \pmod{p} \Longleftrightarrow ( (a_1\cdot b_1) \pmod{p_1}, (a_2\cdot b_2) \pmod{p_2}, \ldots, (a_k\cdot b_k) \pmod{p_k})$.

Существует много различных доказательств китайской теоремы об остатках. Приведём конструктивное доказательство этой теоремы.

Доказательство 1.

Систему (*) можно решить так:

(1) Для $i=1,\ldots, k$ обозначим </math>z_i=p/p_i=p_1\cdot p_2\cdot\ldots\cdot p_{i-1}\cdot p_{i+1}\cdot \ldots\cdot p_k</math>.

(2) Для $i=1,\ldots, k$ обозначим </math>y_i=z_{i}^{-1} \pmod{p_i}</math>. (Заметим, что это всегда можно сделать, поскольку $(z_i, p_i)=1$.

(3) Решением системы является число $x=a_1\cdot y_1\cdot z_1 + \ldots +a_k\cdot y_k\cdot z_k=1$.

Действительно, рассмотрим выражение для $x$ и вычислим, например, $x \equiv a_1 \pmod{p_1}$. Заметим, что $z_i \equiv 0 \pmod{p_1}$ при $i\ne 1$ (это видно из выражения (1) для $z_i$). Таким образом, вычисляя $x \pmod{p_1}$, получаем $x \equiv a_1\cdot y_1\cdot z_1 \pmod{p_1}$. Но из определения </math>y_i</math> (2) следует, что $y_1\cdot z_1 \equiv 1 \pmod{p_1}$, так что получаем $x \equiv a_1 \pmod{p_1}$. То же самое верно для других значений $i$.

Существование доказано.

Доказательство 2.

Найдём число $x, 0\le x < P$, удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа $x$ вида

$x=a_1+p_1\cdot q_1$, где $q_1$ - произвольное целое число.

Для нахождения $q_1$ подставим значение $x$ во второе сравнение системы, после чего получим $x=a_1+p_1\cdot q_1 \equiv a_2 \pmod{p_2}$, откуда $q_1\equiv a_1+p_{1}^{-1}\cdot(a_2-a_1) \pmod{p_2}$,

где $p_{1}^{-1}$ - обратный мультипликативный элемент к $p_1$ по модулю $p_2$. Такой элемент существует, так как $(p_1, p_2)=1$.

Найденное таким образом $q_1$ можно записать в виде

$q_1 =p_{1}^{-1}\cdot (a_2-a_1) + p_2\cdot q_2$

для некоторого целого числа $q_2$.

Подставим значение $q_1$ в выражение $x =a_{1,2}+q_2\cdot p_1\cdot p_2$.

Теперь первые два сравнения могут быть заменены на одно $x =a_{1,2}+q_2\cdot p_1\cdot p_2$.

Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс $(k-1)$ раз, мы в конечном итоге найдём число $x$, удовлетворяющее всем сравнениям исходной системы.

Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение $x', 0\le x' < P$ исходной системы.

Тогда

$\begin{cases}x \equiv a_i \pmod{p_i},\\ x' \equiv a_i \pmod{p_i}\\ \end{cases}$

для всех $i=1,\ldots,k$.

Вычитая почленно из первого сравнения второе, получим истинное сравнение $(x-x') \equiv 0 \pmod{p_i}$, откуда следует, что для всех $i=1,\ldots,k$ $(x-x')$ делится нацело на $p_i$. Но тогда $(x-x')$ делится нацело на $p$,следовательно, $x=x$, так как $|x-x'|<p$.

Теорема доказана.