Китайская теорема об остатках (КТО)

От /

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

Китайская теорема об остатках — одна из древнейших теорем в теории чисел. Её истоки восходят к III–V векам н. э. в Китае.

Первое известное упоминание содержится в труде китайского математика Сунь Цзы (не путать с автором «Искусства войны») — в книге «Сунь Цзы Суань Цзин» («Математический трактат Сунь Цзы»), написанной примерно в III–IV веках.

В этой книге приводится задача: «Найти число, которое при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — остаток 2.«

Современное решение: x≡2 (mod 3), x≡3 (mod 5), x≡2 (mod 7)

Ответ: x=23 .

Эта задача стала классическим примером применения теоремы. Интересно, что аналогичные задачи встречались и в Индии, и в арабском мире, но именно китайское происхождение дало название теореме.

Только в XIX веке европейские математики (Гаусс, Эйлер и др.) дали строгое доказательство и обобщили теорему для произвольного числа модулей.

Калькулятор остатков

Калькулятор остатков

Теория

Теорема позволяет найти число, которое даёт заданные остатки при делении на разные взаимно простые числа.

Пусть даны:

  • натуральные числа m1​,m2​,…,mk​ , которые попарно взаимно просты (то есть НОД любой пары = 1),
  • целые числа a1​,a2​,…,ak​ — остатки.

Тогда существует единственное решение x по модулю M=m1​⋅m2​⋅…⋅mk​ , удовлетворяющее системе:

x≡a1​ (mod m1​)x≡a2 ​(mod m2​)⋮ x≡ak ​(mod mk​)​

То есть, найдётся такое x , и все остальные решения будут отличаться от него на кратные M .

Теорема работает, если модули попарно взаимно просты — то есть у любой пары НОД = 1.

✔️ Можно: 3, 4, 5 → НОД(3,4)=1, НОД(3,5)=1, НОД(4,5)=1 → ✅
❌ Нельзя: 4, 6, 9 → НОД(4,6)=2 → ❌

КТО Решатель

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

Решатель систем сравнений

🧮 Ввод системы

Решение:

—

📊 Визуализация

Все числа
Нужный остаток
Решение

Все решения (0-100):

—

Шаги решения:

Введите систему и нажмите «Решить»

Пошаговый алгоритм

Рассмотрим на примере:

Задача:
Найти x , если

x≡2 (mod 3),x≡3 (mod 5),x≡2 (mod 7)

Шаг 1: Проверить, что модули попарно взаимно просты

3,5,7 — простые числа → взаимно просты → можно применять КТО.

Шаг 2: Найти общее произведение модулей

M=3⋅5⋅7=105

Шаг 3: Для каждого модуля вычислить Mi​=M/mi​

  • M1​=105/3=35
  • M2​=105/5=21
  • M3​=105/7=15

Шаг 4: Найти обратные элементы yi​ , такие что Mi​⋅yi​≡1(mod mi​)

Это значит: найти yi​ , чтобы при умножении Mi​⋅yi​ остаток от деления на mi​ был 1.

  • Для M1​=35 : найти y1​ , чтобы 35⋅y1​≡1(mod 3)
    35≡2 (mod 3) → решаем 2y1​≡1 (mod 3) → y1​=2 (так как 2⋅2=4≡1 )
  • Для M2​=21 : 21≡1 (mod 5) → 1⋅y2​≡1 (mod 5) → y2​=1
  • Для M3​=15 : 15≡1 (mod 7) → 1⋅y3​≡1 (mod 7) → y3​=1

Шаг 5: Вычислить x

x=a1​M1​y1​+a2​M2​y2​+a3​M3​y3 ​(mod M)

Подставляем:

x=2⋅35⋅2+3⋅21⋅1+2⋅15⋅1=140+63+30=233

x≡233 (mod 105)⇒233−2⋅105=233−210=23

✅ Ответ: x=23

Проверка:

  • 23÷3=7 (ост. 2) ✔️
  • 23÷5=4 (ост. 3) ✔️
  • 23÷7=3 (ост. 2) ✔️

Типовые задания

1. Найдите наименьшее натуральное число, которое при делении на 2 даёт остаток 1, на 3 — остаток 2, на 5 — остаток 4.

Решение:

Система: x≡1 (mod 2),x≡2 (mod 3),x≡4 (mod 5)

Модули 2, 3, 5 — взаимно просты.
M=2⋅3⋅5=30

M1​=15 , M2​=10 , M3​=6

Находим обратные:

  • 15y1​≡1 (mod 2) → 15≡1 (mod 2) → y1​=1
  • 10y2​≡1 (mod 3) → 10≡1 (mod 3) → y2​=1
  • 6y3​≡1 (mod 5) → 6≡1 (mod 5) → y3​=1

x=1⋅15⋅1+2⋅10⋅1+4⋅6⋅1=15+20+24=59

59 mod 30=29

✅ Ответ: 29

2. Найдите x , если x≡1 (mod 4),x≡2 (mod 6)

Внимание! Модули 4 и 6 не взаимно просты (НОД(4,6)=2). Значит, КТО нельзя применять напрямую.

Проверим совместность системы:

Пусть x=4k+1 . Подставим во второе сравнение:

4k+1≡2 (mod 6)⇒4k≡1 (mod 6)

Но 4k≡1 (mod 6) не имеет решения, потому что 4 и 6 не взаимно просты, и 1 не делится на НОД(4,6)=2.

❌ Система несовместна — решений нет.

3. Найдите наименьшее трёхзначное число, которое при делении на 7 даёт остаток 5, на 8 — остаток 6, на 9 — остаток 7.

Решение:

x≡5 (mod 7),x≡6 (mod 8),x≡7(mod 9)

Заметим: остаток всегда на 2 меньше модуля → x+2 делится на 7, 8 и 9.

То есть: x+2≡0 (mod 7),(mod 8),(mod 9) → x+2 кратно НОК(7,8,9)

Так как 7, 8, 9 попарно взаимно просты → НОК = 7⋅8⋅9=504

Значит, x+2=504k⇒x=504k−2

Наименьшее трёхзначное:
при k=1 : x=502 — трёхзначное!

✅ Ответ: 502

Самостоятельная работа

  1. Найдите x , если x≡1 (mod 3) , x≡2 (mod 4) , x≡3 (mod 5) .
  2. Найдите наименьшее натуральное x>100 , если x≡2 (mod 5) , x≡3 (mod 7) , x≡4 (mod 9) .
  3. При каких a система x≡1 (mod 6) , x≡a (mod 10) имеет решение?

✅ Ответы:

  1. x=58
  2. x=157
  3. a≡1,3,5,7,9 (mod10) — то есть a нечётное (чтобы x было нечётным, как требует первое сравнение)

Дополнительно

https://mathus.ru/math/crt.pdf

Прокрутить вверх