Китайская теорема об остатках — фундаментальный результат теории чисел, который позволяет решать систему сравнений по взаимно простым модулям. Теорема утверждает: если m₁, m₂, ..., mₖ — попарно взаимно простые числа, то система x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ) имеет единственное решение по модулю M = m₁ × m₂ × ... × mₖ.
Представьте, что вы знаете остатки от деления неизвестного числа на 3, 5 и 7. Теорема гарантирует: существует единственное число от 0 до 104 (3 × 5 × 7 - 1), которое даёт эти остатки. Это как собрать целое число из его "кусочков" по разным модулям.
История и происхождение
Теорема впервые появилась в китайском математическом трактате "Сунь-цзы Суань Цзин" (Математический трактат мастера Сунь-цзы) около III века н.э. Задача звучала так: "Есть предметы, число которых неизвестно. При делении на 3 остаток 2, на 5 остаток 3, на 7 остаток 2. Сколько предметов?"
Европейские математики заново открыли теорему в XIII веке. Леонардо Фибоначчи описал метод решения в книге "Liber Abaci" (1202). Карл Фридрих Гаусс формализовал теорему в "Арифметических исследованиях" (1801), дав строгое доказательство и связав её с кольцами вычетов.
Математическая формулировка
Условие: Модули m₁, m₂, ..., mₖ попарно взаимно просты (НОД(mᵢ, mⱼ) = 1 при i ≠ j).
Система сравнений: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ).
Решение: x = (a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ) mod M, где M = m₁ × m₂ × ... × mₖ, Mᵢ = M / mᵢ, а yᵢ — обратный элемент Mᵢ по модулю mᵢ (Mᵢyᵢ ≡ 1 mod mᵢ).
Пример решения
Решим задачу Сунь-цзы: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
Шаг 1: M = 3 × 5 × 7 = 105. M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15.
Шаг 2: Находим обратные элементы. 35y₁ ≡ 1 (mod 3) → y₁ = 2 (так как 35 × 2 = 70 ≡ 1 mod 3). 21y₂ ≡ 1 (mod 5) → y₂ = 1 (21 × 1 = 21 ≡ 1 mod 5). 15y₃ ≡ 1 (mod 7) → y₃ = 1 (15 × 1 = 15 ≡ 1 mod 7).
Шаг 3: x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23.
Проверка: 23 ≡ 2 (mod 3), 23 ≡ 3 (mod 5), 23 ≡ 2 (mod 7). Ответ: 23 предмета (или 23 + 105k для любого целого k).
Применение в криптографии
В алгоритме RSA китайская теорема ускоряет расшифровку в 4 раза. Вместо вычисления m = c^d mod n (где n = p × q — произведение простых чисел) расшифровывают отдельно по модулям p и q: m₁ = c^dₚ mod p, m₂ = c^dq mod q, затем комбинируют через китайскую теорему. Это снижает нагрузку на процессор смартфонов при работе с HTTPS.
Приложения в вычислительной математике
Быстрая арифметика: Умножение больших чисел (миллионы разрядов) разбивается на вычисления по маленьким модулям. Например, умножение двух 1000-значных чисел можно заменить умножением по модулям 97, 101, 103 (простые числа), затем восстановить результат через теорему.
Параллельные вычисления: Вычисления по разным модулям независимы — их можно распределить между процессорами. Китайская теорема используется в суперкомпьютерах для симуляций квантовой физики.
Обобщения и связь с алгеброй
В абстрактной алгебре теорема формулируется через изоморфизм колец: Z/MZ ≅ Z/m₁Z × Z/m₂Z × ... × Z/mₖZ. Это означает, что кольцо вычетов по модулю M изоморфно прямому произведению колец вычетов по модулям m₁, m₂, ..., mₖ.
Теорема обобщается на кольца главных идеалов и полиномы. Например, в кольце многочленов над полем можно решать системы сравнений f(x) ≡ g₁(x) (mod p₁(x)), f(x) ≡ g₂(x) (mod p₂(x)), если p₁(x) и p₂(x) взаимно просты.
Практическое значение
Китайская теорема об остатках используется в современных процессорах Intel и AMD для операций с большими числами. Алгоритмы цифровой подписи (ECDSA, EdDSA) применяют теорему для ускорения проверки подписей в блокчейне. Каждая биткойн-транзакция проверяется с использованием китайской теоремы — это экономит электроэнергию майнинговых ферм.