Арифметика по кругу: часы и сравнения
На циферблате часов 12 — и это 0 (полночь), и 12, и 24. 13 часов = 1 час. 25 часов = 1 час. Если прибавить 5 к 10, получим не 15, а 3. Это арифметика по модулю 12 — частный случай теории сравнений. Сравнение a ≡ b (mod m) означает: a и b дают одинаковый остаток при делении на m, или эквивалентно, m делит (a−b).
Основные свойства сравнений
Сравнения ведут себя аналогично обычным уравнениям. Если a ≡ b (mod m) и c ≡ d (mod m), то: a+c ≡ b+d (mod m), a·c ≡ b·d (mod m). Можно складывать, вычитать, умножать сравнения. Нельзя просто делить: 6 ≡ 4 (mod 2) ⟹ 3 ≡ 2 (mod 2)? Нет! Деление требует осторожности — необходимо, чтобы делитель был взаимно прост с модулем.
Линейное сравнение ax ≡ b (mod m)
Аналог линейного уравнения в модульной арифметике. Когда оно разрешимо? Линейное сравнение ax ≡ b (mod m) имеет решение тогда и только тогда, когда d = НОД(a, m) делит b. Если решение существует, то их ровно d штук (по модулю m).
Нахождение решения: расширенный алгоритм Евклида даёт числа x₀, y₀ такие, что ax₀ + my₀ = d (теорема Безу). Тогда x = x₀·(b/d) mod (m/d) — одно из решений; остальные отличаются на m/d.
Пример: 3x ≡ 6 (mod 9). d = НОД(3,9) = 3. 3|6? Да. m/d = 3 решения. Один вариант: x = 2 (3·2=6≡6). Все решения: x ≡ 2 (mod 3), то есть x = 2, 5, 8.
Обратный элемент по модулю
Если НОД(a, m) = 1 (a и m взаимно просты), то существует обратный элемент a⁻¹ такой, что a·a⁻¹ ≡ 1 (mod m). Тогда уравнение ax ≡ b (mod m) имеет единственное решение x ≡ a⁻¹·b (mod m). Обратный элемент вычисляется расширенным алгоритмом Евклида. В криптографии RSA нахождение обратного — ключевая операция при генерации секретного ключа.
Системы линейных сравнений: Китайская теорема об остатках
Система: x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), ..., x ≡ rₙ (mod mₙ). Если модули mᵢ попарно взаимно просты, то система имеет единственное решение по модулю M = m₁·m₂·...·mₙ (Китайская теорема об остатках). Это позволяет решать задачи с большими числами, разбивая вычисления на независимые малые части — важно для компьютерной арифметики и криптографии.
Применения: от криптографии до программирования
Хэш-функции в программировании часто используют операцию mod. Криптосистема RSA строится на арифметике по модулю (произведению двух больших простых чисел). Коды с обнаружением ошибок (EAN-13, ISBN) используют контрольную сумму по mod 10. Генераторы псевдослучайных чисел (LCG): xₙ₊₁ = (axₙ + c) mod m. Хранение данных: распределение по ячейкам хэш-таблицы — это операция mod.