Китайская теорема об остатках (КТО) — это классическая теорема теории чисел, утверждающая, что если натуральные модули m₁, m₂, ..., m_k попарно взаимно просты (НОД(m_i, m_j) = 1), то система линейных сравнений x ≡ a₁ (mod m₁), ..., x ≡ a_k (mod m_k) имеет единственное решение по модулю их произведения M = m₁ · m₂ · ... · m_k.
Впервые задачу сформулировал китайский математик Сунь Цзы в III веке: найти число, которое при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — остаток 2. Ответ Сунь Цзы: число 23 (и все числа вида 23 + 105k).
Арифметическую операцию деления рассматривает раздел деление чисел с остатком, каноническую факторизацию модулей производит разложение чисел на простые множители, а аналитическую строгость требуют задачи с параметром.
2. Подставляем во второе сравнение: 3k + 2 ≡ 3 (mod 5) ⇒ 3k ≡ 1 (mod 5).
3. Умножаем на 2 (обратный к 3 mod 5): 6k ≡ 2 ⇒ k ≡ 2 (mod 5).
4. x = 3(5t + 2) + 2 = 15t + 6 + 2 = 15t + 8.
Метрика экзаменационных требований: структура заданий ФИПИ
| Параметр оценивания | Период (2024–2025) | Регламент (2027) |
|---|---|---|
| Условие 1 | x ≡ 2 (mod 3) | При счёте тройками остаётся 2 |
| Условие 2 | x ≡ 3 (mod 5) | При счёте пятёрками остаётся 3 |
| Условие 3 | x ≡ 2 (mod 7) | При счёте семёрками остаётся 2 |
| Ответ Сунь Цзы | x = 23 (mod 105) | Наименьшее положительное число предметов — 23 |
1. Формулировка китайской теоремы об остатках и историческая задача
Получи больше пользы от Skysmart:
-
Подготовься к ОГЭ на пятёрку
-
Подготовься к ЕГЭ на высокие баллы
Записывайся на бесплатные курсы для детей
Решай задания в бесплатном тренажёре ЕГЭ
Формулировка
Пусть
Более того, решение x определено однозначно по модулю M, где
Доказательство
Для простоты начнем с системы из двух уравнений:
Поскольку
Это следует из тождества Безу.
Теперь определим число x:
Проверим, удовлетворяет ли это число уравнениям:
По модулю
По модулю
Таким образом, x удовлетворяет обоим уравнениям. Подобные рассуждения можно обобщить на систему из k уравнений, рассматривая их попарно.
Китайская теорема об остатках играет важную роль в различных областях математики и её приложениях, включая криптографию. Она предоставляет эффективный метод для решения систем линейных уравнений с попарно взаимно простыми модулями.
2. Практикум: разбор реальных задач ОГЭ и ЕГЭ
1. x = 5k + 1.
2. 5k + 1 ≡ 3 (mod 7) ⇒ 5k ≡ 2 (mod 7).
3. Подбираем k: при k = 6: 5·6 = 30 ≡ 2 (mod 7).
4. x = 5·6 + 1 = 31.
Проверка: 31 = 5·6 + 1 = 7·4 + 3.
3. Контрольный чек-лист: на чём срезаются школьники
- Ловушка экзамена: Теорема работает ТОЛЬКО если модули попарно взаимно просты (НОД = 1). Если есть общий делитель, требуется факторизация!
- Ловушка экзамена: Не забывайте указывать период решения M = m₁·m₂: решение единственно только по этому общему модулю.
- Ловушка экзамена: При переносе чисел через знак сравнения знаки меняются по обычным правилам алгебры.
Теория чисел — элитная область математики, дающая максимальные преимущества при поступлении. Преподаватели Skysmart научат решать сравнения по модулю легко и красиво.
На индивидуальных уроках в онлайн-школе Skysmart методисты и действующие эксперты экзаменационной комиссии разбирают все подводные камни темы и доводят решение до автоматизма.
4. Ответы на частые вопросы (FAQ)
Что делать, если модули не взаимно просты?
В этом случае каждый модуль раскладывают на степени простых чисел и проверяют систему на совместность (отсутствие противоречий в остатках).
Где КТО применяется на практике?
В компьютерных вычислениях с длинными числами, алгоритмах шифрования RSA и быстром преобразовании Фурье.
