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

У математиці китайська теорема про остачі (або китайська теорема про лишки) стверджує, що якщо відомі залишки від ділення з остачею цілого числа ${\textstyle n}$ на декілька цілих чисел, то можна однозначно визначити остачу від ділення ${\textstyle n}$ на добуток цих цілих чисел за умови, що дільники є попарно взаємно простими (будь-які два дільники не мають спільних множників, окрім 1).^[1]

Цю теорему іноді називають теоремою Сунь-цзи. Обидві назви походять від першої відомої згадки в Сунь-цзи Суань-цзин^[en], китайському манускрипті, написаному в період між 3-м та 5-м століттями нашої ери. Перша згадка обмежена таким прикладом:

Якщо остача від ділення ${\textstyle n}$ на 3 дорівнює 2, від ділення ${\textstyle n}$ на 5 дорівнює 3, а від ділення ${\textstyle n}$ на 7 дорівнює 2, то можна визначити остачу від ділення ${\textstyle n}$ на 105 (добуток 3, 5, та 7), не знаючи значення ${\textstyle n}$. У цьому прикладі остача дорівнює 23. Крім того, ця остача є єдиним можливим додатним значенням для ${\textstyle n}$ менше ніж 105.

Китайська теорема про остачі широко використовується для обчислень з великими цілими числами, тому що дозволяє замінити обчислення, для якого відома межа величини результату, кількома схожими обчисленнями для невеликих цілих чисел.

Китайська теорема про остачі (виражена через рівності за модулем) справджується для кожної області головних ідеалів. Її узагальнили для будь-яких кілець з формулюванням, що використовує двосторонні ідеали.

Найдавніше відоме формулювання задачі з'явилось у книзі Сунь-цзи Суань-цзин^[en] китайського математика Сунь-цзи у 5-му столітті:^[2]

Є певні предмети, кількість яких невідома. Якщо порахувати їх по три, то залишаться два предмети, якщо по п'ять — три предмети, якщо по сім — два предмети. Скільки всього предметів?^[3]

За сучасними стандартами робота Сунь-цзи не вважалася б теоремою, адже він наводить лише одну конкретну задачу без розв'язку, не кажучи вже про доведення для загального випадку чи алгоритм розв'язання.^[4] Алгоритм розв'язання цієї задачі описав Аріабгата у 6-му столітті.^[5] Часткові випадки китайської теореми про остачу були відомі Брамагупті (7-е століття) та з'являлися у роботі Фібоначчі Книга абака (1202).^[6] Результати були пізніше узагальнені повним розв'язком Да-янь-шу (大衍術) в Математичному трактаті у дев’яти розділах^[en][7], написаному Цінь Цзюшао у 1247 році. На початку 19-го століття трактат був перекладений на англійську мову британським місіонером Олександром Вайлі^[en].^[8]

Поняття рівностей за модулем вперше було запропоновано та використано Карлом Фрідріхом Гауссом у книзі Disquisitiones Arithmeticae 1801 року.^[10] Гаусс проілюстрував китайську теорему про остачі задачею з календарями, а саме: «знайти роки, які мають певний номер періоду відносно сонячного та місячного циклів та римського індикту».^[11] Гаусс ввів метод для розв'язання задачі, який вже використовувався Леонардом Ойлером, але насправді був стародавнім методом, який з'являвся декілька разів.^[12]

Нехай ${\textstyle n_{1},\dots ,n_{k}}$ — натуральні числа, більші за 1 (їх часто називають модулями або дільниками). Позначимо добуток ${\textstyle n_{i}}$ як ${\textstyle N}$.

Китайська теорема про остачі стверджує, що якщо ${\textstyle n_{i}}$ є попарно взаємно простими, і якщо ${\textstyle a_{1},\dots ,a_{k}}$ — цілі числа такі, що ${\textstyle 0\leq a_{i}<n_{i}}$ для кожного ${\textstyle i}$, тоді існує одне й лише одне ціле число ${\textstyle x}$ таке, що ${\textstyle 0\leq x<N}$ і залишок від ділення з остачею ${\textstyle x}$ на ${\textstyle n_{i}}$ дорівнює ${\textstyle a_{i}}$ для кожного ${\textstyle i}$.

Це можна переформулювати у термінах рівностей за модулем: Якщо ${\textstyle n_{i}}$ попарно взаємно прості, а також якщо ${\textstyle a_{1},\dots ,a_{k}}$ — довільні цілі числа, то система

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}},\\&\ \ \vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

має розв'язок, і будь-які два розв'язки, наприклад, ${\textstyle x_{1}}$ та ${\textstyle x_{2}}$, рівні за модулем ${\textstyle N}$, тобто ${\textstyle x_{2}\equiv x_{2}{\pmod {N}}}$.^[13]

В абстрактній алгебрі теорему часто формулюють так: якщо ${\textstyle n_{i}}$ — попарно взаємно прості, то відображення

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\dots ,x{\bmod {n}}_{k})}$

задає ізоморфізм кілець^[14]

${\displaystyle \mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }$

між кільцем цілих чисел за модулем ${\textstyle N}$ та прямим добутком^[en] кілець цілих чисел за модулем ${\textstyle n_{i}}$. Це означає, що замість послідовності арифметичних операцій у ${\textstyle \mathbb {Z} /N\mathbb {Z} }$ можна виконати аналогічні обчислення незалежно у кожному ${\textstyle \mathbb {Z} /n_{i}\mathbb {Z} }$, а потім отримати результат шляхом застосування ізоморфізму (справа наліво). Це може бути значно швидшим способом, ніж пряме обчислення, якщо ${\textstyle N}$ та кількість операцій є великими. Цей підхід широко використовується в лінійній алгебрі для цілих та раціональних чисел під назвою багатомодульне обчислення.

Теорему також можна переформулювати у термінах комбінаторики так: нескінченні арифметичні прогресії цілих чисел утворюють сімейство Хеллі^[en].^[15]

Існування та єдиність розв'язку можна довести незалежно. Однак перший спосіб доведення існування, наведений нижче, використовує цю єдиність.

Припустимо, що ${\textstyle x}$ та ${\textstyle y}$ є розв'язками всіх рівностей за модулем. Оскільки ${\textstyle x}$ та ${\textstyle y}$ мають однакову остачу при діленні на ${\textstyle n_{i}}$, то їх різниця ${\textstyle x-y}$ кратна кожному з ${\textstyle n_{i}}$. А оскільки ${\textstyle n_{i}}$ попарно взаємно прості, то їх добуток ${\textstyle N}$ також є дільником ${\textstyle x-y}$, отже, ${\textstyle x}$ та ${\textstyle y}$ рівні за модулем ${\textstyle N}$. Якщо ${\textstyle x}$ та ${\textstyle y}$ мають бути невід'ємними та меншими за ${\textstyle N}$ (як у першому формулюванні теореми), тоді їхня різниця може кратною ${\textstyle N}$ тільки за умови, що ${\textstyle x=y}$.

Відображення

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\dots ,x{\bmod {n}}_{k})}$

переводить класи рівності за модулем ${\textstyle N}$ у послідовності класів рівності за модулем ${\textstyle n_{i}}$. Доведення єдиності показує, що це відображення є ін'єкцією. Оскільки область визначення та область значень цього відображення мають однакову кількість елементів, то відображення є сюр'єкцією, що доводить існування розв'язку.

Існування може бути встановлене шляхом явної побудови ${\textstyle x}$, яку можна розбити на два етапи: спочатку знаходимо розв'язок задачі у випадку з двома модулями, а потім узагальнюємо розв'язок за допомогою індукції за кількістю модулів.^[16]

Потрібно розв'язати систему:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}}$

де ${\textstyle n_{1}}$ та ${\textstyle n_{2}}$ взаємно прості.

Тотожність Безу стверджує існування такої пари цілих чисел ${\textstyle m_{1}}$ та ${\textstyle m_{2}}$, що

${\displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}$

Цілі числа ${\textstyle m_{1}}$ та ${\textstyle m_{2}}$ можуть бути обчислені за допомогою розширеного алгоритму Евкліда. Запишемо розв'язок у такому вигляді:

${\displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}$

Справді,

${\displaystyle {\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}}$

отже, ${\textstyle x\equiv a_{1}{\pmod {n_{1}}}}$. Друга рівність за модулем доводиться аналогічно, необхідно лише переставити місцями індекси 1 та 2.

Розглянемо послідовність рівностей за модулем:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\ \ \vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

де ${\textstyle n_{i}}$ попарно взаємно прості. Перші дві рівності мають розв'язок ${\textstyle a_{1,2}}$ за способом з попереднього розділу. Множина розв'язків перших двох рівностей є множиною всіх розв'язків рівності

${\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}$

Оскільки інші ${\textstyle n_{i}}$ взаємно прості з ${\textstyle n_{1}n_{2}}$, то розв'язування початкової задачі з ${\textstyle k}$ рівностями зводиться до розв'язування аналогічної задачі з ${\textstyle k-1}$ рівностями. Повторюючи ці дії, ітеративно отримуємо розв'язок початкової задачі.

Для побудови розв'язку не обов'язково використовувати індукцію за кількістю модулів, однак така пряма побудова вимагає більше обчислень з великими числами, тому вона менш ефективна та рідше використовується. Тим не менше, інтерполяційний многочлен Лагранжа є частковим випадком цієї побудови, який застосовується до многочленів замість цілих чисел.

Нехай ${\textstyle N_{i}=N/n_{i}}$ — добуток усіх модулів, крім одного. Оскільки ${\textstyle n_{i}}$ попарно взаємно прості, то ${\textstyle N_{i}}$ та ${\textstyle n_{i}}$ також взаємно прості, тому можемо застосувати тотожність Безу, отже, існують такі цілі числа ${\textstyle M_{i}}$ та ${\textstyle m_{i}}$ такі, що

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

Розв'язком системи рівностей за модулем є

${\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}$

Оскільки ${\textstyle N_{j}}$ є добутком ${\textstyle n_{i}}$, ${\textstyle i\neq j}$, то отримуємо

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

для кожного ${\textstyle i}$.

Нехай ${\displaystyle A,(B_{i})_{i\in I}}$ — комутативні кільця з одиницею, ${\displaystyle \phi _{i}\colon 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/{\biggl (}\bigcap _{i\in I}\operatorname {Ker} \phi _{i}{\biggr )}\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.

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