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

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

Позначимо ${\displaystyle \ M=n_{1}n_{2}\dots n_{k}}$ і ${\displaystyle M_{i}={\frac {M}{n_{i}}}}$. Звідки випливає взаємна простота ${\displaystyle n_{i}}$ і ${\displaystyle M_{i}}$. Тож за допомогою розширеного алгоритму Евкліда можна знайти такі ${\displaystyle f_{i},\ g_{i}\in \mathbb {Z} }$, що

${\displaystyle f_{i}n_{i}+g_{i}M_{i}=1.}$

Позначимо ${\displaystyle e_{i}=g_{i}M_{i}}$. Тоді ${\displaystyle e_{i}\equiv 1\ ({\bmod {\ }}n_{i})}$ в той час, як ${\displaystyle e_{i}\equiv 0\ ({\bmod {\ }}n_{j})}$ якщо ${\displaystyle j\neq i}$. Визначивши ${\displaystyle x}$ за допомогою суми

${\displaystyle x=\sum _{i=1}^{k}y_{i}e_{i}}$

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

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

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

${\displaystyle \Phi (a)=(\phi _{i}(a))_{i\in I}}$

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

${\displaystyle A/(\cap _{i\in I}\operatorname {Ker} \,\phi _{i})\simeq \prod _{i\in I}B_{i}}$.

Якщо взяти ${\displaystyle A=\mathbb {Z} /(a_{1}\cdot \ldots \cdot a_{n})\mathbb {Z} }$, ${\displaystyle B_{i}=\mathbb {Z} /a_{i}\mathbb {Z} }$ і визначити гомоморфізми наступним чином

${\displaystyle \phi _{i}(x)=x\mod a_{i},}$

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

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

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

• Реалізація алгоритму на мові C#
• Втілення алгоритму на мові C++