Просмотр исходного текста страницы Китайская теорема об остатках

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

Теорема. 

Пусть <math>p_1, p_2, \ldots, p_k</math> - попарно взаимно простые числа, большие 1, и пусть <math>P = p_1 \cdot p_2 \cdot \ldots  \cdot p_k</math>. Тогда существует единственное неотрицательное решение по модулю <math>P</math> следующей системы сравнений:
: <math>x \equiv a_1 \pmod{p_1}</math>,
: <math>x \equiv a_2 \pmod{p_2}</math>,
: <math>\ldots</math>,
: <math>x \equiv a_k \pmod{p_k}</math>.

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

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

если

:<math>a \Longleftrightarrow (a_1, \ldots, a_k)</math>,

:<math>b \Longleftrightarrow (b_1, \ldots, b_k)</math>,

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

: <math>(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})</math>,

: <math>(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})</math>,

: <math>(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})</math>.


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

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

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

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

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

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

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

<math>q_1 =p_{1}^{-1}\cdot (a_2-a_1) + p_2\cdot q_2</math>

для некоторого целого числа <math>q_2</math>. 

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

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

Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k-1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы. 

Тогда

:<math>\begin{cases}x \equiv a_i \pmod{p_i},\\
x' \equiv a_i \pmod{p_i}\\
\end{cases}</math>

для всех <math>i=1,\ldots,k</math>.

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

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