Китайская теорема об остатках — различия между версиями

Версия 12:03, 2 сентября 2014

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

Теорема.

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

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

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

Найдём число $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', 0\le x' < P$ исходной системы. Тогда

@@ Строка 29: / Строка 29: @@
 Существует много различных доказательств китайской теоремы об остатках. Приведём конструктивное доказательство этой теоремы.
+Доказательство.
+Найдём число <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> исходной системы. Тогда

Китайская теорема об остатках — различия между версиями

Версия 12:03, 2 сентября 2014

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты