Линейное сравнение: когда деление даёт несколько ответов

Если умеешь решить сравнение с необратимым коэффициентом, листай до «Теперь сам».

Как думаешь, где потерялись ответы

Нужно найти x, для которого 8·x при делении на 20 даёт остаток 12. Обратного к восьмёрке по модулю 20 нет: общий делитель равен четырём. Значит ли это, что задача не имеет решения? Попробуй x = 4: произведение 32 действительно даёт 12. Невозможность обратного действия говорит о неоднозначности восстановления, а не об обязательном отсутствии ответа.

В прошлых уроках деление через обратный элемент решало только взаимно простой случай. Теперь разберём оставшийся: проверим существование, найдём один ответ и перечислим все, не подменяя это перебором миллиарда кандидатов.

На что это похоже

Представь циферблат на двадцать делений. Стрелка каждый раз перескакивает на восемь отметок. Из нуля она попадает только в отметки, кратные четырём. До 12 добраться можно, до 10 нельзя. После пяти прыжков положение повторится, хотя счётчик прыжков продолжает расти. Поэтому одному положению соответствуют несколько значений счётчика в диапазоне от нуля до девятнадцати.

Механизм: общий делитель и уменьшенный циферблат

Сравнение означает равенство a·x - m·y = b для некоторого целого y. Левая часть делится на d, потому что на него делятся и a, и m. Если правая не делится, равенство невозможно. Это необходимая проверка до любых поисков обратного.

Если b делится на d, получаем a'·x ≡ b' (mod m'), где штрих означает деление на d. Числа a' и m' взаимно просты: иначе общий делитель исходной пары был бы больше d. Теперь расширенный Евклид даёт коэффициент u из a'·u + m'·v = 1, а один ответ равен b'·u mod m'.

К этому ответу можно прибавлять m': произведение a·m' кратно m, поскольку a кратно d. В диапазоне [0, m) помещается ровно d таких значений. Других нет: разность двух решений после сокращения обязана делиться на m', потому что коэффициент a' обратим.

Правило

При m > 0 сравнение имеет решение ровно тогда, когда НОД(a, m) делит b. Все ответы по модулю m имеют вид x₀ + k·m/d, где 0 ≤ k < d и 0 ≤ x₀ < m/d. При m/d = 1 единственный остаток уменьшенной задачи равен нулю; искать обратный не нужно.

Разбор: четыре решения вместо отсутствующего обратного

Для 8·x ≡ 12 (mod 20) получаем 2·x ≡ 3 (mod 5). Обратный к двум равен трём. Значит x₀ = 9 mod 5 = 4. Поднимаем ответ с шагом пять: 4, 9, 14, 19. Каждое произведение даёт остаток 12. Цена перечисления действительно зависит от четырёх ответов: напечатать их быстрее четырёх действий нельзя.

from math import gcd


def egcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s


def solve(a, b, m):
    assert m > 0
    a %= m
    d = gcd(a, m)
    if b % d:
        return []
    step = m // d
    if step == 1:
        x0 = 0
    else:
        _, inverse = egcd(a // d, step)
        x0 = (b // d * inverse) % step
    return [x0 + k * step for k in range(d)]


print(solve(8, 12, 20))
print(solve(8, 10, 20))
print(solve(0, 0, 4))
checked = 0
for m in range(1, 21):
    for a in range(m):
        for b in range(-m, m + 1):
            actual = solve(a, b, m)
            brute = [x for x in range(m) if (a * x - b) % m == 0]
            assert actual == brute
            checked += 1
print("Проверено:", checked)

[4, 9, 14, 19]
[]
[0, 1, 2, 3]
Проверено: 5950

Код проверяет и формулу, и полноту на малых модулях независимым перебором. Этот перебор нужен в проверке, а не в рабочем алгоритме. Расширенный Евклид делает логарифмическое число делений; выдача всех решений требует ещё d действий. Здесь считаем арифметические операции, а не битовую цену длинных целых.

Разбор: отрицательная правая часть и нулевой коэффициент

8·x ≡ -8 (mod 20) после сокращения превращается в 2·x ≡ -2 (mod 5). Отрицательная правая часть не меняет доказательство: остаток Python приводит результат к диапазону уменьшенного модуля. Получатся те же четыре решения, что для правой части 12.

Если коэффициент ноль, сравнение становится 0 ≡ b (mod m). При кратном m числе b подходят все m остатков, иначе ни одного. В программе это естественно обрабатывается случаем m' = 1. Для модуля один есть ровно один класс остатков, представленный нулём; не нужно объявлять такой вход ошибочным.

Что ломается без этого

Сократить только коэффициент и правую часть, оставив модуль 20, нельзя: так ты решишь другую задачу. И наоборот, один найденный ответ ещё не все ответы исходного сравнения. Уменьшенный модуль хранит период решений, исходный задаёт диапазон их перечисления. Проверяй эти две роли отдельно.

Зачем это в работе

Кольцевой буфер имеет двадцать ячеек, запись перемещается на восемь за операцию. Требуется узнать все номера операций в одном двадцатишаговом окне, когда запись попадёт в заданную ячейку. Сравнение сразу отделяет недостижимую ячейку от нескольких допустимых моментов. Та же арифметика появляется при согласовании периодических расписаний и восстановлении счётчиков по остаткам.

Теперь сам

Реши 9·x ≡ 6 (mod 15). Сколько ответов останется, если заменить 6 на 7?