Лінійне конгруентне рівняння

Це рівняння має вигляд:

$$a \cdot x \equiv b \pmod n,$$

де $a$, $b$ і $n$ — задані цілі числа, а $x$ — невідоме ціле число.

Потрібно знайти значення $x$ з проміжку $[0, n-1]$ (зрозуміло, що на всій числовій прямій може бути нескінченно багато розв'язків, які відрізнятимуться один від одного на $n \cdot k$, де $k$ — будь-яке ціле число). Якщо розв'язок не єдиний, то ми розглянемо, як отримати всі розв'язки.

Коли підходить цей алгоритм?

• Чи рівняння має вигляд конгруенції $a \cdot x \equiv b \pmod n$ з одним невідомим $x$? (якщо це звичайне рівняння $ax + by = c$ в цілих → Лінійне діофантове рівняння)
• Чи відомий розклад $\gcd(a, n)$, тобто можна перевірити, чи $g = \gcd(a, n)$ ділить $b$ (інакше розв'язку немає)?
• Чи достатньо звести задачу до оберненого елемента за модулем, а не до системи конгруенцій з різними модулями? (якщо модулів кілька → Китайська теорема про остачі)

Розв'язок через знаходження оберненого елемента

Спершу розглянемо простіший випадок, коли $a$ і $n$ є взаємно простими ($\gcd(a, n) = 1$). Тоді можна знайти обернений елемент до $a$, і, помноживши обидві частини рівняння на цей обернений елемент, ми отримаємо єдиний розв'язок.

$$x \equiv b \cdot a ^ {- 1} \pmod n$$

Тепер розглянемо випадок, коли $a$ і $n$ не є взаємно простими ($\gcd(a, n) \ne 1$). Тоді розв'язок існуватиме не завжди (наприклад, $2 \cdot x \equiv 1 \pmod 4$ не має розв'язку).

Нехай $g = \gcd(a, n)$, тобто найбільший спільний дільник чисел $a$ і $n$ (який у цьому випадку більший за одиницю).

Тоді, якщо $b$ не ділиться на $g$, розв'язку немає. Справді, для будь-якого $x$ ліва частина рівняння $a \cdot x \pmod n$ завжди ділиться на $g$, тоді як права частина на нього не ділиться, звідки випливає, що розв'язків немає.

Якщо ж $g$ ділить $b$, то, поділивши обидві частини рівняння на $g$ (тобто поділивши $a$, $b$ і $n$ на $g$), ми отримаємо нове рівняння:

$$a^\prime \cdot x \equiv b^\prime \pmod{n^\prime}$$

у якому $a^\prime$ і $n^\prime$ вже взаємно прості, а такі рівняння ми вже навчилися розв'язувати. Як розв'язок для $x$ ми отримуємо $x^\prime$.

Зрозуміло, що цей $x^\prime$ буде розв'язком і вихідного рівняння. Проте він не буде єдиним розв'язком. Можна показати, що вихідне рівняння має рівно $g$ розв'язків, і виглядатимуть вони так:

$$x_i \equiv (x^\prime + i\cdot n^\prime) \pmod n \quad \text{for } i = 0 \ldots g-1$$

Підсумовуючи, можемо сказати, що кількість розв'язків лінійного конгруентного рівняння дорівнює або $g = \gcd(a, n)$, або нулю.

Розв'язок за допомогою розширеного алгоритму Евкліда

Ми можемо переписати лінійну конгруенцію у вигляді такого діофантового рівняння:

$$a \cdot x + n \cdot k = b,$$

де $x$ і $k$ — невідомі цілі числа.

Метод розв'язування цього рівняння описано у відповідній статті Лінійні діофантові рівняння, і він полягає у застосуванні розширеного алгоритму Евкліда.

Там також описано метод отримання всіх розв'язків цього рівняння з одного знайденого розв'язку, і, до речі, цей метод, якщо в нього уважно вдуматися, абсолютно еквівалентний методу, описаному в попередньому розділі.

Відеоматеріали