Китайская теорема об остатках - История изменений

Isaeva в 09:51, 4 февраля 2015

2015-02-04T09:51:25Z

Isaeva в 09:15, 4 февраля 2015

2015-02-04T09:15:50Z

Isaeva в 11:47, 11 сентября 2014

2014-09-11T11:47:15Z

Isaeva в 12:27, 4 сентября 2014

2014-09-04T12:27:03Z

Isaeva в 20:04, 2 сентября 2014

2014-09-02T20:04:57Z

Isaeva в 14:23, 2 сентября 2014

2014-09-02T14:23:18Z

Isaeva в 12:38, 2 сентября 2014

2014-09-02T12:38:27Z

Isaeva в 12:03, 2 сентября 2014

2014-09-02T12:03:36Z

Isaeva: Новая страница: «Китайская теорема об остатках формулируется следующим образом: Теорема. Пусть $p_1, p_2…»$

2014-09-02T09:10:13Z

Новая страница: «Китайская теорема об остатках формулируется следующим образом: Теорема. Пусть <math>p_1, p_2…»

Новая страница

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

Теорема.

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

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

@@ Строка 5: / Строка 5: @@
 Пусть <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>x \equiv a_2 \pmod{p_2}</math>,     (*)
-: <math>\ldots</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>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>, можно эквивалентно выполнять над соответствующими элементами кортежами путём независимого выполнения операций над каждым компонентом:
@@ Строка 39: / Строка 40: @@
 Систему (*) можно решить так:
-(1) Для <math>i=1,\ldots, k</math> обозначим <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>.
+(1) Для <math>i=1,\ldots, k</math> обозначим <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) Для <math>i=1,\ldots, k</math> обозначим <math>y_i=z_{i}^{-1} \pmod{p_i}</math>. (Заметим, что это всегда можно сделать, поскольку <math>(z_i, p_i)=1</math>.
@@ Строка 45: / Строка 46: @@
 (3) Решением системы является число <math>x=a_1\cdot y_1\cdot z_1 + \ldots +a_k\cdot y_k\cdot z_k=1</math>.
-Действительно, рассмотрим выражение для <math>x</math> и вычислим, например, <math>x \equiv a_1 \pmod{p_1}</math>. Заметим, что <math>z_i \equiv 0 \pmod{p_1}</math> при <math>i\ne 1</math> (это видно из выражения (1) для <math>z_i</math>). Таким образом, вычисляя <math>x \pmod{p_1}</math>, получаем <math>x \equiv a_1\cdot y_1\cdot z_1 \pmod{p_1}</math>. Но из определения </math>y_i</math> (2) следует, что <math>y_1\cdot z_1 \equiv 1 \pmod{p_1}</math>, так что получаем <math>x \equiv a_1 \pmod{p_1}</math>.
 То же самое верно для других значений <math>i</math>.
@@ Строка 94: / Строка 97: @@
 Вычитая почленно из первого сравнения второе, получим истинное сравнение <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>.
+откуда следует, что для всех <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>.
 ''Теорема доказана.''
@@ Строка 111: / Строка 114: @@
 ''Решение''
-Так как модули <math>13, 15, 19</math> - попарно взаимно простые числа, то данная система имеет единственное решение по модулю <math>P = 13\cdot 15\cdot 19 = 3705</math>. Сравнение <math>x = 1 \pmod{13}</math> соответствует диофантову уравнению <math>x = 1 + 13\cdot t</math>, где <math>t \in Z</math>.
+Так как модули <math>13, 15, 19</math> попарно взаимно просты, то данная система имеет единственное решение по модулю <math>P = 13\cdot 15\cdot 19 = 3705</math>. Сравнение <math>x = 1 \pmod{13}</math> соответствует диофантову уравнению <math>x = 1 + 13\cdot t</math>, где <math>t \in Z</math>.
 Заменяя <math>x</math> во втором сравнении системы на <math>1 + 13\cdot t</math>, получаем <math>1 + 13\cdot t \equiv 4 \pmod{15}</math>, т.е. <math>13\cdot t \equiv 3 \pmod{15}</math>.
@@ Строка 117: / Строка 120: @@
 К числу <math>13</math> обратным мультипликативным элементом по модулю <math>15</math> является число <math>7</math>. Умножая последнее сравнение на <math>7</math> и переходя в нём к вычетам по модулю 15, получим <math>t \equiv 6 \pmod{15}</math>. Таким образом, <math>t = 6 + 15\cdot u</math>, где <math>u \in Z</math>.
-Следовательно, <math>x = 1 + 13\cdot t = 1+13 \cdot (6 + 15 \cdot u) = 79 + 195 \cdot u</math>, при этом все числа вида <math>x = 79 + 195 \cdot u, u \in Z</math> являются решениями первых двух сравнений данной системы. Подставим в третье сравнение вместо <math>x</math> полученное выше значение <math>79 + 195 \cdot u</math>:
+Следовательно, <math>x = 1 + 13\cdot t = 1+13 \cdot (6 + 15 \cdot u) = 79 + 195 \cdot u</math>, при этом все числа вида <math>x = 79 + 195 \cdot u, u \in Z</math> являются решениями первых двух сравнений данной системы.
-:<math>79 + 195 \cdot u \equiv 8 \pmod{19}</math> или <math>5 \cdot u \equiv 5 \pmod{19}</math>.
+:<math>79 + 195 \cdot u \equiv 8 \pmod{19}</math>,
-Так как <math>(5, 19) = 1</math>, то <math>u \equiv 1 \pmod{19}</math>, или <math>u = 1 + 19 \cdot v, v \in Z</math>.
+Так как <math>(39, 19) = 1</math>, то <math>u \equiv 1 \pmod{19}</math>, или <math>u = 1 + 19 \cdot v, v \in Z</math>.
 Итак,
 :<math>79 + 195 \cdot u = 79 + 195 \cdot (1 + 19 \cdot v) = 274 + 3705 \cdot v</math>, т.е. <math>x = 274</math>.

@@ Строка 1: / Строка 1: @@
 Китайская теорема об остатках формулируется следующим образом:
-Теорема.
+'''Теорема'''.
 Пусть <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> следующей системы сравнений:
@@ Строка 32: / Строка 32: @@
-Доказательство существования.
+''Доказательство существования.''
 Доказательство 1.
 Систему (*) можно решить так:
@@ Строка 47: / Строка 48: @@
 То же самое верно для других значений <math>i</math>.
-Существование решения доказано.
+''Существование решения доказано.''
 Доказательство 2.
 Найдём число <math>x, 0\le x < P</math>, удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа <math>x</math> вида
@@ Строка 76: / Строка 78: @@
 Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k-1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
-Существование решения доказано.
+''Существование решения доказано.''
-Доказательство единственности.
+''Доказательство единственности.''
 Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы.
@@ Строка 94: / Строка 96: @@
 откуда следует, что для всех <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>.
-Теорема доказана.
+''Теорема доказана.''

@@ Строка 38: / Строка 38: @@
 Систему (*) можно решить так:
-(1) Для <math>i=1,\ldots, k</math> обозначим </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>.
+(1) Для <math>i=1,\ldots, k</math> обозначим <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) Для <math>i=1,\ldots, k</math> обозначим </math>y_i=z_{i}^{-1} \pmod{p_i}</math>. (Заметим, что это всегда можно сделать, поскольку <math>(z_i, p_i)=1</math>.
+(2) Для <math>i=1,\ldots, k</math> обозначим <math>y_i=z_{i}^{-1} \pmod{p_i}</math>. (Заметим, что это всегда можно сделать, поскольку <math>(z_i, p_i)=1</math>.
 (3) Решением системы является число <math>x=a_1\cdot y_1\cdot z_1 + \ldots +a_k\cdot y_k\cdot z_k=1</math>.

@@ Строка 8: / Строка 8: @@
 : <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>.
@@ Строка 29: / Строка 30: @@
 Существует много различных доказательств китайской теоремы об остатках. Приведём конструктивное доказательство этой теоремы.
 Доказательство 1.
@@ Строка 43: / Строка 47: @@
 То же самое верно для других значений <math>i</math>.
-Существование доказано.
+Существование решения доказано.
 Доказательство 2.
@@ Строка 72: / Строка 76: @@
 Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k-1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
 Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы.

@@ Строка 5: / Строка 5: @@
 Пусть <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>x \equiv a_2 \pmod{p_2}</math>,  (*)
 : <math>\ldots</math>,
 : <math>x \equiv a_k \pmod{p_k}</math>.
@@ Строка 30: / Строка 30: @@
 Существует много различных доказательств китайской теоремы об остатках. Приведём конструктивное доказательство этой теоремы.
-Доказательство.
+Доказательство 1.
 Найдём число <math>x, 0\le x < P</math>, удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа <math>x</math> вида
@@ Строка 56: / Строка 71: @@
 Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k-1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
 Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы.

← Предыдущая		Версия 14:23, 2 сентября 2014
Строка 67:		Строка 67:

	Вычитая почленно из первого сравнения второе, получим истинное сравнение <math>(x-x') \equiv 0 \pmod{p_i}</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>.
		+
		+	Теорема доказана.

@@ Строка 55: / Строка 55: @@
 <math>x =a_{1,2}+q_2\cdot p_1\cdot p_2</math>.
-Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k–1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
+Применим теперь описанную процедуру к полученному сравнению и к одному из оставшихся сравнений исходной системы. Повторяя этот процесс <math>(k-1)</math> раз, мы в конечном итоге найдём число <math>x</math>, удовлетворяющее всем сравнениям исходной системы.
-Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы. Тогда
+Докажем единственность решения. Воспользуемся методом от противного. Предположим, что существует другое решение <math>x', 0\le x' < P</math> исходной системы.

← Предыдущая		Версия 12:03, 2 сентября 2014
Строка 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> исходной системы. Тогда