Калькулятор китайської теореми про остачі
Розв'язує систему одночасних порівнянь за модулем за китайською теоремою про остачі. Введіть остачі та попарно взаємно прості модулі, щоб отримати найменший невід'ємний розв'язок.
Розв'язувач китайської теореми про остачі
Формула китайської теореми про остачі
Де:
- \(a_i\) — остачі (значення, з якими \(x\) має бути конгруентним)
- \(n_i\) — модулі; вони мають бути попарно взаємно простими (найбільший спільний дільник будь-яких двох із них дорівнює 1)
- \(N\) — добуток усіх модулів; за взаємно простих модулів він дорівнює їхньому найменшому спільному кратному
- \(N_i\) — добуток усіх модулів, крім \(n_i\)
- \(y_i\) — обернений за модулем елемент \(N_i\) за модулем \(n_i\), тобто число, для якого \(N_i y_i \equiv 1 \pmod{n_i}\)
- \(x\) — єдиний розв'язок за модулем \(N\)
Теорема стверджує, що коли модулі попарно взаємно прості, система має рівно один розв'язок у діапазоні \(0 \le x < N\). Формула будує цей розв'язок, поєднуючи кожну остачу з оберненим елементом до відповідного часткового добутку.
Китайська теорема про остачі — приклад обчислення
Приклад: знайти \(x\) таке, що \(x \equiv 2 \pmod{3}\) і \(x \equiv 3 \pmod{5}\) — це стандартні значення калькулятора.
\[ N = 3 \times 5 = 15 \]
\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{оскільки } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]
\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{оскільки } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]
\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]
Результат: \(x = 8\) за модулем \(15\). Дійсно, \(8 \div 3 = 2\) з остачею \(2\), а \(8 \div 5 = 1\) з остачею \(3\), тож обидва порівняння виконуються. Наступний розв'язок — \(8 + 15 = 23\), потім \(38\) і так далі.
Як користуватися калькулятором
- Введіть кількість порівнянь (щонайменше 2). Додаткові пари «остача–модуль» з'являться автоматично.
- Для першого порівняння введіть остачу в поле остача 1 (\(a_1\)), а модуль — у поле модуль 1 (\(n_1\)).
- Повторіть для остачі 2 / модуля 2 та будь-яких інших пар.
- Зчитайте найменший невід'ємний розв'язок \(x\) та модуль (НСК модулів) \(N\). Кожне число виду \(x + kN\) (\(k = 0, 1, 2, \dots\)) також задовольняє систему.
Що таке китайська теорема про остачі?
Китайська теорема про остачі (КТО) — класичний результат теорії чисел, уперше описаний китайським математиком Сунь-цзи приблизно в III–V столітті н. е. Вона відповідає на питання: якщо відомо кілька дільників та остачі, які лишаються після ділення невідомого числа на кожен із них, чи можна відновити це число? Теорема стверджує, що так — за умови, що модулі попарно взаємно прості — і що відповідь є єдиною в діапазоні, довжина якого дорівнює добутку всіх модулів.
Наочний приклад: якщо в кошику \(x\) яєць і, рахуючи їх по 3, отримуємо остачу 2, а, рахуючи по 5, — остачу 3, то \(x \equiv 2 \pmod{3}\) і \(x \equiv 3 \pmod{5}\). КТО однозначно визначає \(x\) за модулем 15 — у цьому випадку \(x = 8, 23, 38, \dots\)
Теорема важлива тим, що показує: система багатьох малих порівнянь еквівалентна одному порівнянню з великим модулем. Це дає змогу замінити арифметику з дуже великим модулем паралельною арифметикою з кількома малими, зручними модулями, а потім об'єднати результати. Крок об'єднання використовує обернені за модулем елементи, які можна обчислити окремо за допомогою калькулятора оберненого за модулем; обернені такого типу пов'язані також з малою теоремою Ферма та теоремою Ейлера.
Інтерпретація результату
Калькулятор повертає найменший невід'ємний розв'язок \(x\) та комбінований модуль \(N\). Повний набір розв'язків — це \(x, x + N, x + 2N, \dots\); якщо у вашій задачі мають сенс від'ємні відповіді, підійдуть також \(x - N\) і менші значення. Оскільки розв'язок єдиний за модулем \(N\), два різні набори вхідних даних, які дають однакове \(x \pmod{N}\), описують ту саму систему.
Припущення та обмеження
- Потрібні попарно взаємно прості модулі. Жодна пара модулів не повинна мати спільного дільника, більшого за 1; інакше калькулятор видасть помилку. Якщо, скажімо, два модулі — 4 і 6 (обидва діляться на 2), система може не мати розв'язку взагалі або мати кілька розв'язків за їхнім НСК.
- Узгодженість системи. За взаємно простих модулів теорема завжди дає розв'язок — у цьому й сила КТО. Суперечності між порівняннями можуть виникати лише тоді, коли умову взаємної простоти порушено.
- Остачі можуть перевищувати модуль. Вхідні дані виду \(a = 7, n = 5\) трактуються як \(7 \equiv 2 \pmod 5\); калькулятор автоматично зводить остаточну відповідь за модулем \(N\).
- Модулі мають бути додатними цілими числами. Значення 0 та від'ємні числа відхиляються.
- Великі системи. Оскільки \(N\) — добуток усіх модулів, він зростає дуже швидко. За великої кількості модулів числа можуть перевищити діапазон, у якому стандартна арифметика з плаваючою комою є точною.
Де застосовується КТО
Окрім чистої теорії чисел, КТО є робочим інструментом у кількох галузях. У криптографії вона прискорює розшифрування RSA, обчислюючи результат окремо за кожним простим множником і потім об'єднуючи його; вона також лежить в основі порогових схем, як-от схема розподілу секрету Шаміра. В інформатиці вона дає змогу створювати системи залишкових класів, які виконують додавання та множення паралельно на малих модулях, і застосовується в хешуванні, плануванні та календарних обчисленнях — класичних задачах «підрахунку солдатів по шеренгах», які й стали першоджерелом праці Сунь-цзи.
Часті запитання
Як розв'язати систему за КТО вручну, без формули?
Для двох порівнянь можна скористатися підстановкою: візьміть перше, тобто x = a₁ + k·n₁ для цілих \(k\). Підставте в друге порівняння, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), і розв'яжіть відносно \(k\), знайшовши обернений елемент \(n_1\) за модулем \(n_2\). Потім підставте \(k\) назад, щоб отримати \(x\), і зведіть за модулем \(n_1 n_2\). Цей метод послідовної підстановки працює для будь-якої кількості порівнянь, розв'язуючи їх по два за раз.
Що станеться, якщо модулі не попарно взаємно прості?
Коли два модулі мають спільний дільник, система може бути неузгодженою й не мати розв'язку взагалі. Розв'язок існує лише тоді, коли остачі сумісні: для кожної пари \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). Якщо вони сумісні, розв'язок усе одно єдиний, але лише за найменшим спільним кратним модулів, а не за їхнім добутком. Умова взаємної простоти гарантовано забезпечує існування розв'язку, тому цей калькулятор відхиляє такі вхідні дані.
Чому розв'язок єдиний і як знайти всі інші розв'язки?
Єдиність випливає з того, що коли два числа \(x\) і \(x'\) обидва задовольняють систему, їхня різниця ділиться на кожен модуль, а отже, й на їхній добуток \(N\) (бо вони взаємно прості). Тому \(x \equiv x' \pmod{N}\), тобто в діапазоні \(0 \le x < N\) існує рівно один розв'язок. Усі інші розв'язки мають вигляд \(x + kN\) для будь-якого цілого \(k\), зокрема від'ємні значення на кшталт \(x - N\), якщо ваша задача їх допускає.
Чи можуть остачі бути від'ємними або більшими за модуль?
Так. Остачу, більшу за її модуль, автоматично зводять — наприклад, \(a = 7\) за \(n = 5\) — це те саме, що \(a = 2\). Від'ємні остачі теж працюють: \(x \equiv -1 \pmod{5}\) означає те саме, що \(x \equiv 4 \pmod{5}\). Остаточну відповідь завжди нормалізують до найменшого невід'ємного представника в діапазоні \(0 \le x < N\).
Як знайти обернений елемент за модулем вручну?
Скористайтеся розширеним алгоритмом Евкліда: виконайте звичайний алгоритм Евкліда для \(N_i\) і \(n_i\), а потім ідіть у зворотному напрямку, щоб подати \(\gcd = 1\) у вигляді \(uN_i + vn_i\). Коефіцієнт \(u\) задовольняє \(uN_i \equiv 1 \pmod{n_i}\), тож \(y_i = u \bmod n_i\). Для простого модуля \(p\) можна також застосувати малу теорему Ферма: \(y_i \equiv N_i^{p-2} \pmod{p}\).
Які типові помилки при застосуванні китайської теореми про остачі?
Найчастіші помилки: використання модулів, які не є попарно взаємно простими (наприклад, 4 і 6, що мають спільний дільник 2); плутання полів остачі й модуля під час введення даних; забування про те, що відповідь — це клас розв'язків, а не одне число; введення модуля 1, що формально допустимо, але не додає інформації. Також перевірте, чи остачі відповідають вашій задачі — \(x \equiv 2 \pmod{3}\) не те саме, що \(x \equiv 3 \pmod{2}\).
Чи є швидкий спосіб перевірити відповідь калькулятора?
Так — просто розділіть відповідь на кожен модуль і перевірте остачі. Якщо результат \(x\), перевірте, що \(x \bmod n_i = a_i \bmod n_i\) для кожного порівняння у вашій системі. Друга перевірка: обчисліть \(x \bmod N\) іншим способом, наприклад послідовною підстановкою, і переконайтеся, що отримали те саме значення. Якщо обидві перевірки пройдено, розв'язок правильний, адже єдиність за модулем \(N\) гарантує, що іншої відповіді в цьому діапазоні немає.