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

Китайська теорема про залишки — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати наступним чином. Нехай $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$ , заданий формулою