Математика / Арифметика и теория чисел

Китайская теорема об остатках для двух взаимно простых модулей

Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}

Схема Кандидаты x = 2 + 5t по модулю 7

Только 17 среди этих представителей даёт остаток 3.

Обозначения

$x$: искомое целое число, безразмерная величина
m, n: взаимно простые модули, безразмерная величина
r, s: заданные остатки по m и n соответственно, безразмерная величина
$m⁻¹$: обратный к m по модулю n, безразмерная величина

Условия применения

Исходные сравнения имеют вид x≡r mod m и x≡s mod n. Модули m,n — целые больше единицы, НОД(m,n)=1. В формуле m⁻¹ берётся именно по модулю n; выражение в скобках выбирается как остаток от 0 до n−1.

Ограничения

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

Подробное объяснение

Первое сравнение позволяет записать все его решения как x=r+mt, где t целое. Подставим эту запись во второе сравнение: mt≡s−r по модулю n. Взаимная простота модулей гарантирует существование обратного к m по модулю n.

Умножение на обратный даёт t≡(s−r)m⁻¹ mod n. Выбрав любой представитель t, подставляем его в r+mt. Если изменить t на n, число x изменится на mn, поэтому все найденные решения образуют один класс по произведению модулей.

Для доказательства единственности возьмём два решения. Их разность делится и на m, и на n. При взаимной простоте она делится на mn, значит решения совпадают по этому модулю. В диапазоне от нуля до mn−1 остаётся ровно один представитель.

Перестановка двух сравнений меняет ход вычисления и используемый обратный элемент, но не окончательный класс. Это удобная дополнительная проверка для небольшой задачи. Быстрее всё же подставить полученное число в оба исходных деления.

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

Как пользоваться формулой

Проверьте взаимную простоту модулей и запишите исходные остатки относительно одного начала отсчёта.
Представьте решение первого сравнения как r+mt и перенесите r во второе сравнение по модулю n.
Найдите обратный к m по модулю n и умножьте на разность s−r, чтобы определить остаток t.
Вычислите r+mt, приведите ответ по модулю mn и независимо проверьте оба первоначальных остатка.

Историческая справка

Название теоремы связано с китайской математической традицией задач о числе, заданном остатками при делении. Учебник Barrus и Clark указывает на Sunzi Suanjing, датируемый периодом между III и V веками нашей эры, как ранний источник подобных задач. Современная формулировка использует язык сравнений и взаимно простых модулей, а вычислительная запись опирается на обратные элементы. Это более общий и систематический язык, чем отдельная историческая задача. В современной алгебре и вычислительной теории чисел результат связывает расчёты по одному большому модулю с расчётами по нескольким меньшим. Здесь разбирается только случай двух целых модулей; обобщения на несколько модулей и другие алгебраические структуры сохраняют идею согласования локальных остатков.

Историческая линия формулы

Название отражает раннюю китайскую традицию задач об остатках. Исторический текст и современная формула через модульный обратный относятся к разным формам изложения; приведённая запись не выдаётся за буквальную нотацию древнего источника.

Пример

Решим x≡2 (mod 5), x≡3 (mod 7). Положим x = 2+5t. Тогда 5t≡1 (mod 7); обратный к 5 равен 3, значит t≡3. Получаем x = 17. Проверка: 17 = 3 · 5+2 и 17 = 2 · 7+3. Так как НОД(5,7) = 1, все решения x = 17+35k. Остаток 17 в диапазоне 0,…,34 выбран как представитель класса. Добавление 35 сохраняет оба сравнения, потому что 35 делится и на 5, и на 7. Ни один другой остаток этого диапазона не имеет одновременно пары (2,3), что подтверждает единственность. Проверка обоих остатков обязательна: одно совпадение с первым модулем ещё не решает систему.

Частая ошибка

Не используйте обратный к n по модулю m в формуле, выведенной для обратного к m по n. Не забывайте разность s−r. Не называйте единственным целое решение: единственен только класс по mn. Не применяйте произведение модулей как период без проверки взаимной простоты.

Практика

Задачи с решением

Два остатка

Условие. Решите x≡1 mod 3 и x≡2 mod 5.

Решение. Пишем x=1+3t. Тогда 3t≡1 mod 5; обратный к 3 равен 2. t≡2, поэтому x≡7 mod 15.

Ответ. x=7+15k, k целое

Проверка представителя

Условие. Найдите наименьшее неотрицательное x при x≡3 mod 4 и x≡1 mod 5.

Решение. x=3+4t, значит 4t≡−2≡3 mod 5. Обратный к 4 равен 4: t≡12≡2. x=11; остатки 3 и 1.

Ответ. 11, общий класс 11 mod 20

Дополнительные источники

https://encyclopediaofmath.org/wiki/Chinese_remainder_theorem
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%253A_Chapters/1.23%253A_Chinese_Remainder_Theorem

Связанные формулы

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Функция Эйлера: произведение по простым делителям

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

Математика

Наибольший общий делитель

$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$

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