Китайська теорема про залишки

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Китайська теорема про залишки — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати наступним чином. Нехай  y_1,y_2, \dots, y_k довільні цілі числа, а n_1, n_2, \dots, n_k попарно взаємно прості числа. Тоді наступна система:

x \equiv y_1\ (\bmod\ n_1)
x \equiv y_2\ (\bmod\ n_2)
\vdots
x \equiv y_k\ (\bmod\ n_k)

має розв'язок і всі її розв'язки рівні за модулем M = n_1n_2\dots n_k

Історія[ред.ред. код]

Близько 100 р. до н.е. китайський математик Сун Цу (Sun-Tsŭ) розв'язав таку задачу: знайти число, яке дає при діленні на 3, 5 та 7 остачі 2, 3 та 2 відповідно (загальний розв'язок має вигляд 23+105k для цілих k). Тому твердження про еквівалентність системи порівнянь за взаємно простими модулями, і порівняння за модулем добутку називають "китайською теоремою про залишки".

Конструктивне доведення[ред.ред. код]

Позначимо \ M = n_1n_2\dots n_k і M_i = \frac{M}{n_i}. Звідки випливає взаємна простота n_i і M_i. Тож за допомогою розширеного алгоритму Евкліда можна знайти такі f_i,\ g_i \in \Z, що

f_i n_i + g_i M_i = 1

Позначимо e_i = g_i M_i. Тоді e_i \equiv 1\ (\bmod\ n_i) в той час, як e_i \equiv 0\ (\bmod\ n_j) якщо j \ne i. Визначивши x за допомогою суми

x = \sum_{i=1}^{k} y_i e_i

одержуємо необхідний розв'язок. Очевидно всі числа рівні йому за модулем M теж є розв'язками. Якщо взяти тепер два довільні розв'язки x^1,x^2, то, згідно з умовами теореми, їхня різниця повинна ділитися на кожне з чисел n_i, а значить, враховуючи попарну взаємну простоту чисел n_1, n_2, \dots, n_k, і на їхній добуток. Тобто:

x^1-x^2 \equiv 0\ (\bmod\ M), що завершує доведення теореми.

Алгебраїчна версія[ред.ред. код]

Нехай A, (B_i)_{i \in I} — комутативні кільця з одиницею, \phi_i: A \to B_i сюр'єктивні гомоморфізми, такі що Ker\,\phi_i + Ker\,\phi_j=A для всіх i,j \in I. Тоді гомоморфізм \Phi: A \to \prod_{i \in I} B_i, заданий формулою

\Phi(a) = (\phi_i(a))_{i \in I}

є сюр'єктивним. Окрім того, \Phi визначає ізоморфізм

A / (\cap_{i \in I} Ker\,\phi_i )\simeq \prod_{i \in I} B_i.

Якщо взяти A=\mathbb{Z}/(a_1\cdot \ldots \cdot a_n)\mathbb{Z}, B_i = \mathbb{Z}/a_i\mathbb{Z} і визначити гомоморфізми наступним чином

\phi_i(x) = x \mod a_i

то ми одержуємо арифметичну версію теореми.

Див. також[ред.ред. код]

Джерела[ред.ред. код]