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

Число при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — остаток 2. Что это за число? Перебирая числа по одному, через некоторое время дойдёте до 23, но в вопросе скрыта теорема: пока у делителей нет общего множителя, ниже их произведения всегда есть ровно один ответ, и его можно найти без перебора. Теореме около 1 500 лет, и она по-прежнему работает в календарях, в компьютерной арифметике и в криптографии, которая защищает интернет.

Три ряда отметок для чисел с остатками 2 mod 3, 3 mod 5 и 2 mod 7, сходящихся в одном столбце на числе 23
Три ряда отметок для чисел с остатками 2 mod 3, 3 mod 5 и 2 mod 7, сходящихся в одном столбце на числе 23

Задача из «Сунь-цзы суань цзин»

«Сунь-цзы суань цзин», китайская книга по арифметике III–V веков, спрашивает о числе предметов, которое при счёте тройками даёт остаток 2, пятёрками — 3, семёрками — 2. Её ответ — 23, а метод учат до сих пор: берите 70 за каждый предмет, оставшийся при счёте тройками, 21 — за каждый при счёте пятёрками и 15 — за каждый при счёте семёрками, сложите и вычитайте 105, сколько получится. 2 × 70 + 3 × 21 + 2 × 15 = 233, а 233 − 2 × 105 = 23. Стихи эпохи Мин веками хранили в памяти числа 70, 21, 15 и 105. Цинь Цзюшао дал общий метод в 1247 году, та же задача есть в «Книге абака» Фибоначчи 1202 года, а Карл Фридрих Гаусс сформулировал теорему в современном виде в «Арифметических исследованиях» 1801 года.

Страница цинского издания «Сунь-цзы суань цзин», китайского арифметического трактата III–V веков, где требуется число, дающее остатки 2, 3 и 2 при счёте тройками, пятёрками и семёрками.
Страница цинского издания «Сунь-цзы суань цзин», китайского арифметического трактата III–V веков, где требуется число, дающее остатки 2, 3 и 2 при счёте тройками, пятёрками и семёрками.
Карл Фридрих Гаусс на портрете Кристиана Альбрехта Йенсена 1840 года. Обозначение сравнения a ≡ b (mod n) он ввёл в Disquisitiones Arithmeticae 1801 года.
Карл Фридрих Гаусс на портрете Кристиана Альбрехта Йенсена 1840 года. Обозначение сравнения a ≡ b (mod n) он ввёл в Disquisitiones Arithmeticae 1801 года.

Что утверждает теорема

Возьмите модули n₁, n₂, …, nₖ, никакие два из которых не имеют общего делителя, и любые остатки a₁, a₂, …, aₖ. Тогда существует ровно одно целое число x от 0 до N − 1, где N = n₁ × n₂ × … × nₖ, которое при делении на nᵢ даёт остаток aᵢ для каждого i. Все остальные решения отличаются от него на кратное N. На языке модульной арифметики: система x ≡ aᵢ (mod nᵢ) имеет решение, и оно единственно по модулю N. Иначе говоря, число от 0 до N − 1 и список его остатков несут в точности одну и ту же информацию: 3 × 5 × 7 = 105 чисел и 3 × 5 × 7 = 105 возможных списков остатков, каждый используется один раз.

Как построить решение

Числа 70, 21 и 15 — не волшебство. Каждое из них даёт остаток 1 при делении на свой модуль и остаток 0 при делении на остальные: 70 = 2 × 35 кратно 5 и 7 и при делении на 3 даёт остаток 1. В общем случае берут Nᵢ = N / nᵢ, кратное всем модулям, кроме nᵢ, и умножают на yᵢ — обратный к Nᵢ по модулю nᵢ. Обратный существует, потому что у Nᵢ и nᵢ нет общего делителя, и его находит расширенный алгоритм Евклида: он выполняет деления Евклида для наибольшего общего делителя и возвращается назад к соотношению Безу 1 = s × nᵢ + t × Nᵢ, так что t и есть обратный. Тогда x = a₁N₁y₁ + a₂N₂y₂ + …, приведённое по модулю N, удовлетворяет каждому сравнению, потому что каждое слагаемое подходит к своему сравнению и исчезает во всех остальных.

Сравнения по одному

Есть второй способ, которому не нужно произведение всех модулей. Каждое решение x ≡ 2 (mod 3) имеет вид x = 2 + 3t. Подставим это в следующее сравнение: 2 + 3t ≡ 3 (mod 5), то есть 3t ≡ 1 (mod 5), и умножение на 2, обратный к 3 по модулю 5, даёт t ≡ 2 (mod 5). Тогда x = 2 + 3 × 2 = 8, и первые два сравнения вместе говорят x ≡ 8 (mod 15). Повторим с третьим сравнением: 8 + 15t ≡ 2 (mod 7) даёт t ≡ 1, поэтому x ≡ 23 (mod 105). Такая подстановка держит числа меньше, именно так компьютер обычно решает подобные системы, и она работает и тогда, когда у модулей есть общий делитель.

Модули с общим делителем

Если у двух модулей есть общий делитель, их сравнения перекрываются: x ≡ 1 (mod 4) уже говорит, что x нечётно, а x ≡ 4 (mod 6) — что x чётно, поэтому никакое x не удовлетворяет обоим. В общем случае x ≡ a (mod m) и x ≡ b (mod n) выполняются одновременно ровно тогда, когда a и b дают одинаковый остаток при делении на g = gcd(m, n), то есть когда g делит a − b. Тогда решение единственно по модулю lcm(m, n) = m × n / g, а не по модулю m × n. Старая задача про корзину с яйцами, из которой при выкладывании по 2, 3, 4, 5 или 6 остаётся 1, а по 7 — ничего, имеет ответ 301, повторяющийся через каждые 420 = lcm(2, 3, 4, 5, 6, 7). Система имеет решение ровно тогда, когда каждые два её сравнения согласованы, поэтому в несовместной системе всегда есть противоречащая пара.

Календари, компьютеры и RSA

В 1583 году Жозеф Скалигер объединил три календарных цикла — 28-летний солнечный цикл, 19-летний лунный цикл и 15-летний индикт — в юлианский период длиной 28 × 19 × 15 = 7 980 лет. По теореме у каждого года своё сочетание трёх номеров цикла, а период начинается в 4713 году до н. э., последнем году, когда все три номера равнялись 1; астрономы до сих пор отсчитывают от него юлианские дни. Компьютеры используют теорему, чтобы вычислять с огромными числами как со списками малых остатков, которые можно складывать и умножать по отдельности и параллельно, а в конце соединить. Расшифровка RSA устроена так же: c^d mod n при n = p × q вычисляется как два возведения в степень по модулям p и q, соединённые теоремой, примерно в четыре раза быстрее, чем одно возведение по модулю n. Схемы разделения секрета, например схемы Миньотта и Асмута — Блума, прячут секрет в остатках так, что раскрыть его может только достаточное их число вместе.

Рон Ривест, Ади Шамир и Лен Адлеман (слева направо)
Рон Ривест, Ади Шамир и Лен Адлеман (слева направо)

Попробуйте сами

Откройте калькулятор, чтобы ввести любую систему сравнений, до 20 сравнений и числа до 200 цифр, или выберите один из разобранных примеров: задачу Сунь-цзы, корзину с яйцами, юлианский период, расписания двух автобусов, расшифровку RSA и систему без решения. Решение расписано на ваших числах, конструкцией или подстановкой, с расширенным алгоритмом Евклида для каждого обратного. Рисунок отмечает числа, удовлетворяющие каждому сравнению, чтобы был виден единственный столбец, где сходятся все, или раскладывает остатки двух сравнений в таблицу, где у каждого числа своя клетка.

Часто задаваемые вопросы

Единственно ли решение системы сравнений?

Только с точностью до кратного модулю. Если x = 23 решает задачу Сунь-цзы, то её решают и 23 + 105 = 128, 233 и −82, потому что прибавление 105 не меняет ни одного остатка. Теорема говорит, что от 0 до 104 решение ровно одно; при модулях с общими делителями — ровно одно ниже их наименьшего общего кратного.

Почему модули должны быть взаимно простыми?

Для конструкции — потому что у Nᵢ должен быть обратный по модулю nᵢ, а он существует только при отсутствии общего делителя. Для самой теоремы — потому что общие делители заставляют некоторые сравнения перекрываться: тогда система либо не имеет решений, либо имеет меньше различных, и решения повторяются через наименьшее общее кратное, а не через произведение.

Как найти обратный по модулю вручную?

Расширенным алгоритмом Евклида. Для обратного к 15 по модулю 7: 15 = 2 × 7 + 1, значит, 1 = 15 − 2 × 7 и 15 × 1 ≡ 1 (mod 7): обратный равен 1. Для 35 по модулю 3: 35 = 11 × 3 + 2 и 3 = 1 × 2 + 1, значит, 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, и обратный к 35 по модулю 3 равен −1 ≡ 2. Для маленьких модулей можно и просто перебирать 1, 2, 3, …, пока произведение не даст остаток 1.

При чём тут часы?

Остаток по модулю n — это положение стрелки на часах с n делениями. Двое часов с 3 и 5 делениями, запущенные вместе и сдвигаемые на одно деление за шаг, покажут каждую из 15 пар положений по одному разу, прежде чем вернутся к началу, потому что у 3 и 5 нет общего делителя. Часы с 4 и 6 делениями возвращаются через 12 шагов и показывают только 12 из 24 пар: нечётное и чётное положения никогда не встречаются вместе.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть калькулятор китайской теоремы об остатках