Китайська теорема про остачі

Кита́йська теоре́ма про оста́чі — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати таким чином. Нехай $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_{1}n_{2}\dots n_{k}$.

Історія

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

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

Позначимо $\ M=n_{1}n_{2}\dots n_{k}$ і $M_{i}={\frac {M}{n_{i}}}$. Звідки випливає взаємна простота $n_{i}$ і $M_{i}$. Тож за допомогою розширеного алгоритму Евкліда можна знайти такі $f_{i},\ g_{i}\in \mathbb {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\neq 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}$ сюр'єктивні гомоморфізми, такі що $\operatorname {Ker} \,\phi _{i}+\operatorname {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}\operatorname {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},$

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

Див. також

• Діофантові рівняння
• Алгоритм Евкліда

Література

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
• Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. — МЦНМО: БИНОМ. — С. 960. — ISBN 5-900916-37-5.

Джерела

Українською

• (укр.) Гаврилків В. М. Елементи теорії груп та теорії кілець. — І.-Ф.  : Голіней, 2023. — 153 с.
• Реалізація алгоритму на мові C# [Архівовано 11 Червня 2010 у Wayback Machine.]
• Втілення алгоритму на мові C++ [Архівовано 27 Серпня 2016 у Wayback Machine.]