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

Метод состоит в том, что систему сравнений с попарно взаимно простыми модулями заменяют одним сравнением по произведению этих модулей. Китайская теорема об остатках (КТО) гарантирует, что такая система всегда имеет единственное решение по модулю $M = m_1 m_2 \cdots m_k$.

Интуиция: представь, что тебе надо синхронизировать несколько независимых циферблатов с $m_1$, $m_2$, $m_3$ делениями. КТО говорит: ты всегда можешь настроить один большой циферблат с $M = m_1 m_2 m_3$ делениями так, чтобы он давал нужное показание на каждом малом. Это похоже на согласование расписаний: если автобусы ходят с периодом 3 часа и 5 часов, они встретятся через 15 часов — и зная, когда именно, можно рассчитать любое взаимодействие.

КТО используется в двух направлениях: (1) анализ — разбить сложное сравнение по модулю $M$ на несколько простых по его простым множителям; (2) синтез — из набора условий «$x$ даёт остаток $r_i$ при делении на $m_i$» восстановить $x$. В олимпиадах чаще встречается аналитическое применение: доказать существование числа с заданным набором делимостей.

• КТО (формулировка): пусть $m_1, m_2, \ldots, m_k$ попарно взаимно просты и $M = m_1 m_2 \cdots m_k$. Тогда для любого набора остатков $r_1, r_2, \ldots, r_k$ система$$x \equiv r_1 \pmod{m_1},\quad x \equiv r_2 \pmod{m_2},\quad \ldots,\quad x \equiv r_k \pmod{m_k}$$ имеет единственное решение по модулю $M$. Условие: модули попарно взаимно просты. Когда использовать: всегда, когда задача сводится к системе сравнений с такими модулями.

• Формула явного решения: $x \equiv \sum_{i=1}^k r_i \cdot M_i \cdot (M_i^{-1} \bmod m_i) \pmod{M}$, где $M_i = M/m_i$. Когда использовать: при конструктивном нахождении числа по системе условий.

• Изоморфизм колец: $\mathbb{Z}/M\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \times \cdots \times \mathbb{Z}/m_k\mathbb{Z}$. Когда использовать: при доказательстве теорем о существовании, когда нужно работать с каждой компонентой отдельно.

• Разложение модуля на взаимно простые множители. Если $M = p_1^{a_1} \cdots p_k^{a_k}$, то сравнение по $M$ равносильно системе сравнений по $p_i^{a_i}$. Используй это для упрощения.

• Конструкция числа с заданными делимостями. Надо найти $x$, кратное $a$, но не кратное $b$: записываешь $x \equiv 0 \pmod{a}$, $x \not\equiv 0 \pmod{b}$, применяешь КТО.

• Доказательство существования через КТО. Хочешь показать, что существует простое в промежутке $[a,b]$ вида $4k+3$: систему сравнений задаёшь так, чтобы нужные условия выполнялись.

• Нахождение периода комбинированного условия. Если явление повторяется с периодом $m_1$ и независимо с периодом $m_2$, совместное повторение имеет период $m_1 m_2$ (при $\gcd(m_1,m_2)=1$).

• Проверка условия взаимной простоты. Перед применением КТО убедись, что модули попарно взаимно просты — это единственное существенное ограничение.

Поверхностные признаки (что буквально написано):
- «Докажите, что существует натуральное число, оканчивающееся на ... и делящееся на ...»
- «Найдите число, дающее остаток $r_1$ при делении на $m_1$ и остаток $r_2$ при делении на $m_2$»
- «Докажите, что таких чисел бесконечно много»

Структурные признаки (форма выражения, объекты):
- В задаче одновременно фигурируют несколько независимых условий делимости
- Модули взаимно просты (часто это простые числа или их степени)
- Задача о периодических последовательностях с несколькими периодами

Цель задачи (что от тебя хотят):
- Доказать существование числа (или бесконечно многих чисел) с заданными свойствами делимости
- Найти конкретное число, удовлетворяющее системе условий
- Описать все числа с данным набором остатков

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

Источник: тренировочная (классический пример КТО)

Как думать (рассуждение ученика$):
1. $Что вижу?* Система из трёх условий на остатки. Модули $3, 5, 7$ попарно взаимно просты — это КТО!$2. *$Что делаю? Применяю формулу: $M = 3 \cdot 5 \cdot 7 = 105$. Вычислю $x$ по формуле КТО.$3. *$Конкретные шаги:* $M_1 = 35$, $M_2 = 21$, $M_3 = 15$. Нахожу обратные: $35^{-1} \bmod 3$: $35 \equiv 2 \pmod 3$, $2^{-1} \equiv 2 \pmod 3$. Аналогично остальные.

Решение:

Система: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$. $M = 105$.

$M_1 = 35$: $35 \equiv 2 \pmod 3$, $2^{-1} \equiv 2 \pmod 3$. Вклад: $2 \cdot 35 \cdot 2 = 140$.$M_2 = 21$: $21 \equiv 1 \pmod 5$, $1^{-1} = 1$. Вклад: $3 \cdot 21 \cdot 1 = 63$.$M_3 = 15$: $15 \equiv 1 \pmod 7$, $1^{-1} = 1$. Вклад: $2 \cdot 15 \cdot 1 = 30$.

$x \equiv 140 + 63 + 30 = 233 \equiv 233 - 2 \cdot 105 = 23 \pmod{105}$.

Проверка: $23 = 3 \cdot 7 + 2$ ✓; $23 = 5 \cdot 4 + 3$ ✓; $23 = 7 \cdot 3 + 2$ ✓.

Ответ: $23$.

Что в этой задаче было главным: формула КТО работает механически — главное проверить условие взаимной простоты модулей и правильно найти обратные элементы.

Задача 2. Докажите, что среди любых $105$ последовательных натуральных чисел найдётся число, делящееся одновременно на $3$, на $5$ и на $7$.

Источник: тренировочная (иллюстрация КТО)

Как думать (рассуждение ученика$):
1. $Что вижу?* Среди $105 = 3 \cdot 5 \cdot 7$ последовательных чисел — это полный период по модулю $105$. Каждый класс вычетов по $\bmod 105$ встречается ровно один раз.$2. *$Что хочу найти? Число, кратное $3$, $5$ и $7$ одновременно, то есть кратное $105$. Это класс $x \equiv 0 \pmod{105}$.

Решение:

Среди $105$ последовательных натуральных чисел каждый из $105$ классов вычетов по модулю $105$ встречается ровно один раз. Класс $x \equiv 0 \pmod{105}$ представлен ровно одним числом. По КТО условия $x \equiv 0 \pmod{3}$, $x \equiv 0 \pmod{5}$, $x \equiv 0 \pmod{7}$ совместны и имеют решение $x \equiv 0 \pmod{105}$ — кратное $105$.

Ответ: такое число всегда есть, и оно единственно в рассматриваемой серии.

Что в этой задаче было главным: КТО гарантирует, что каждая комбинация остатков встречается в полном периоде ровно раз.

• Ошибка: применять КТО к модулям, не являющимся попарно взаимно простыми (например, $m_1 = 6$, $m_2 = 4$). → Почему неверно: КТО в стандартной форме требует попарной взаимной простоты. → Как избежать: разложи каждый модуль на степени простых и работай с ними.

• Ошибка: неправильно находить обратный элемент $M_i^{-1} \bmod m_i$. → Почему неверно: обратный существует только если $\gcd(M_i, m_i) = 1$, что гарантировано при правильном выборе. → Как избежать: всегда проверяй $M_i \bmod m_i \neq 0$ и находи обратный расширенным алгоритмом Евклида или перебором.

• Ошибка: считать, что КТО работает при любых остатках, когда модули не взаимно просты. → Почему неверно: если $\gcd(m_1, m_2) = d > 1$, система $x \equiv r_1 \pmod{m_1}$, $x \equiv r_2 \pmod{m_2}$ имеет решение тогда и только тогда, когда $r_1 \equiv r_2 \pmod d$. → Как избежать: при несовместных модулях — проверяй условие совместности.

• Ошибка: забыть взять решение по модулю $M$ в конце. → Почему неверно: решение единственно лишь по модулю $M$. → Как избежать: в конце всегда бери остаток от деления на $M$.