Калькулятор китайской теоремы об остатках

Добро пожаловать в калькулятор китайской теоремы об остатках — мощный инструмент теории чисел, который решает системы одновременных сравнений. Независимо от того, изучаете ли вы модульную арифметику, готовитесь к математическим олимпиадам, работаете над задачами криптографии или исследуете теорию чисел, этот калькулятор предоставит полное пошаговое решение с интерактивной визуализацией, показывающей, как классы вычетов выравниваются в уникальном решении.

Что такое китайская теорема об остатках?

Китайская теорема об остатках (КТО) — это фундаментальный результат теории чисел, который гарантирует существование и единственность решения системы одновременных сравнений при условии, что модули попарно взаимно просты. Теорема была впервые описана китайским математиком Сунь-цзы (孫子) в его труде Сунь-цзы Суаньцзин (孫子算經) примерно в III веке нашей эры.

Формально, для системы:

Если все модули \(m_1, m_2, \ldots, m_k\) попарно взаимно просты (т. е. \(\gcd(m_i, m_j) = 1\) для всех \(i \neq j\)), то существует единственное решение \(x\) по модулю \(M = m_1 \times m_2 \times \cdots \times m_k\).

Как работает алгоритм КТО

Конструктивное доказательство лежит в основе алгоритма, используемого этим калькулятором:

Шаг 1: Вычисление M

Вычислите произведение всех модулей:

Шаг 2: Вычисление каждого Mᵢ

Для каждого сравнения \(i\) вычислите \(M_i = M / m_i\). Это произведение всех модулей, кроме \(m_i\).

Шаг 3: Поиск модульных инверсий

Для каждого \(i\) найдите \(y_i\) такое, что \(M_i \cdot y_i \equiv 1 \pmod{m_i}\), используя расширенный алгоритм Евклида. Поскольку \(M_i\) и \(m_i\) взаимно просты, эта инверсия всегда существует.

Шаг 4: Построение решения

Общее решение имеет вид \(x + k \cdot M\) для любого целого \(k\), что означает повторение решения через каждые \(M\) целых чисел.

Как пользоваться этим калькулятором

1. Введите ваши сравнения: Для каждого уравнения \(x \equiv a \pmod{m}\) введите остаток \(a\) и модуль \(m\). Начните с 2 сравнений и нажмите «Добавить сравнение» для большего количества (до 10).
2. Проверьте модули: Все модули должны быть положительными целыми числами ≥ 2 и попарно взаимно простыми. Калькулятор проверяет это автоматически.
3. Нажмите «Решить систему»: Калькулятор применит алгоритм КТО и покажет уникальное решение вместе с пошаговым ходом работы.
4. Изучите визуализацию: Числовая прямая показывает, как классы вычетов из каждого уравнения пересекаются в точке решения.
5. Проверьте: Раздел проверки подтверждает, что решение удовлетворяет каждому исходному сравнению.

Понимание результатов

• Наименьшее неотрицательное решение (x₀): Уникальное решение в диапазоне [0, M−1].
• Общее решение: Все целые числа вида x₀ + kM, где k — любое целое число.
• Таблица проверки: Подтверждает, что x₀ mod mᵢ = aᵢ для каждого сравнения.
• Пошаговый разбор: Показывает Mᵢ, модульную инверсию yᵢ и частичную сумму aᵢ·Mᵢ·yᵢ для каждого уравнения.
• Числовая прямая: Визуальное представление того, как классы вычетов выравниваются в решении.

Применения китайской теоремы об остатках

Классическая задача Сунь-цзы

Оригинальная задача из Сунь-цзы Суаньцзин звучит так: «Имеются вещи, число их неизвестно. Если считать их тройками, то остаток 2; если считать пятерками, то остаток 3; если считать семерками, то остаток 2. Сколько вещей?»

Это переводится как: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Используя КТО, получаем ответ x = 23 (и в общем виде 23 + 105k для любого неотрицательного целого k).

Когда КТО не применяется?

• Невзаимно простые модули: Если любая пара модулей имеет общий делитель больше 1, стандартная КТО не гарантирует решения. Решение может существовать, если остатки совместимы, но этот калькулятор требует попарно взаимно простых модулей для стандартного алгоритма.
• Одиночное сравнение: КТО требует как минимум 2 сравнения. Одиночное сравнение \(x \equiv a \pmod{m}\) уже имеет тривиальное решение x = a.

Расширенный алгоритм Евклида

Расширенный алгоритм Евклида необходим для КТО, так как он позволяет найти модульную инверсию. Для целых чисел \(a\) и \(b\) он находит такие целые числа \(x\) и \(y\), что:

Когда \(\gcd(a, b) = 1\), тогда \(x\) является модульной инверсией \(a\) по модулю \(b\), то есть \(a \cdot x \equiv 1 \pmod{b}\).

Часто задаваемые вопросы

Что такое китайская теорема об остатках?

Китайская теорема об остатках (КТО) утверждает, что если у вас есть система одновременных сравнений x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), где все модули попарно взаимно просты, то существует единственное решение по модулю M = m₁ × m₂ × ... × mₖ.

Что значит попарно взаимно простые числа?

Попарно взаимно простые означает, что любая пара модулей не имеет общих делителей, кроме 1. Например, {3, 5, 7} попарно взаимно просты, потому что gcd(3,5)=1, gcd(3,7)=1 и gcd(5,7)=1. Однако {4, 6, 5} НЕ являются попарно взаимно простыми, так как gcd(4,6)=2.

Как решить систему сравнений пошагово?

Чтобы решить с помощью КТО: (1) Проверьте, что модули попарно взаимно просты. (2) Вычислите M = произведение всех модулей. (3) Для каждого сравнения вычислите Mᵢ = M/mᵢ. (4) Найдите модульную инверсию yᵢ для Mᵢ по модулю mᵢ. (5) Вычислите x = Σ(aᵢ × Mᵢ × yᵢ) mod M.

Где применяется китайская теорема об остатках?

КТО применяется в криптографии RSA для ускорения дешифрования, в компьютерной арифметике для работы с большими числами, в кодах с исправлением ошибок и в задачах планирования циклических событий.

Что произойдет, если модули не взаимно просты?

В этом случае стандартная КТО не применяется. Решение может существовать только при условии согласованности остатков с НОД модулей. В противном случае система будет несовместной.

Дополнительные ресурсы

• Китайская теорема об остатках — Википедия
• Расширенный алгоритм Евклида — Википедия
• Модульная арифметика — Википедия