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

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

Теорема.

Пусть $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})$.

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