Линейное диофантово уравнение, часть 2

Теперь, в дополнение к методу «вынесения наименьшего», я расскажу о другом лично изобретённом велосипеде из школьных времён — методе решения линейного диофантова уравнения, который я всегда для себя называл «хождением по кругу».

Предназначен он для решения уравнений вида \(Pn=Qm+R\), где оба коэффициента \(P\) и \(Q\) положительны, причём хотя бы один из них сравнительно невелик (не превосходит пары десятков, и будем для определённости считать, что это \(Q\), меньший по сравнению с \(P\)), а \(0<R<Q<P\) (если \(R=0\), то решать вообще нечего). Уравнение всегда можно привести к такому виду, и чуть позже мы увидим, как это делается.

Итак, нам нужно решить в целых числах уравнение

\[ Pn=Qm+R\tag{1} \]

Слева записано число, кратное \(P\); справа записан тот факт, что остаток от его деления на \(Q\) равен \(R\). Очевидно, этот остаток меньше самого \(Q\). Запишем по кругу числа \(0,1,2,\ldots,(Q-1)\) и как-нибудь отметим среди них \(R\). Рядом с нулём припишем ещё один нуль.

Теперь посчитаем остаток от деления \(P/Q\). Возле получившегося числа припишем единичку.

Заметим, на сколько позиций и в какую сторону произошёл сдвиг между числами, к которым мы приписали нуль и единичку. От числа с приписанной единицей сдвинемся в соответствующую сторону на соответствующее число позиций и припишем там двойку. Будем продолжать тем же образом: сдвинемся ещё раз и припишем тройку и т.д.

Процесс завершится одним из двух способов:

  • очередное число окажется приписанным возле отмеченного \(R\) — тогда приписанное число и есть искомое \(n\);
  • очередное число окажется приписанным возле какой-то ранее сделанной приписки, при этом возле \(R\) ничего не приписано — тогда решения не существует.

Разберём этот метод на примере уравнения

\[ 13n=8m+3\tag{2} \]

Его словесная интерпретация такова: найти кратное 13 число, которое при делении на 8 даёт в остатке 3.

Пишем по кругу числа от 0 до 7 (на рисунке они снаружи), тройку выделяем. Возле нуля подписываем нуль (на рисунке подписи идут внутри). Так как деление 13/8 даёт в остатке 5, подписываем единицу возле пятёрки.


Замечаем, что при таком переходе произошёл перескок через две цифры против часовой стрелки. Продолжаем перескакивать подобным образом, каждый раз подписывая последовательно увеличивающиеся числа: двойку, тройку и т.д. Всё это закончится тем, что мы подпишем семёрку возле выделенного числа 3. Это означает, что решением является \(n=7\), откуда уже легко находим \(m=11\).

Найденное решение, однако, является лишь частным: существует ещё множество пар чисел \((n,m)\), удовлетворяющих уравнению (2). Чтобы найти общее решение, обратим внимание на следующее.

Если прибавить к обеим частям (2) произвольное число, кратное как 13, так и 8, то равенство не нарушится. Такие числа, очевидно, имеют вид \(13\cdot8\cdot k\): поскольку 13 и 8 взаимно просты, их наименьшее общее кратное равно их произведению.

Записываем:

\[ 13n + 13\cdot8k = 8m + 8\cdot13k + 3 \]

\[ 13(n+8k) = 8(m+13k) + 3 \]

Зная частное решение \(n=7\) и \(m=11\), получаем отсюда ответ: общим решением является \(n=7+8k\) и \(m=11+13k\).

Предложенный метод является, по существу, переборным, но прекрасно работает для небольших \(Q\), а представление остатков в виде числового круга позволяет практически полностью избежать вычислений (кроме нахождения одного остатка от деления \(P/Q\), других расчётов не требуется). Его описание является и его обоснованием: увеличение множителя на единицу всякий раз добавляет одно и то же число к остатку, при этом остаток накапливается циклически со сбросом в тот момент, когда накопленное превышает делитель.

Теперь рассмотрим более сложный случай. Пусть нужно решить уравнение

\[ 17n=1027m+913 \]

Оно выглядит как (1), но соотношения между коэффициентам не такие, как указано выше. Перенесём свободный коэффициент в другую часть:

\[ 1027m=17m-913 \]

Тоже плохо: он стал отрицательным и по модулю превосходит 17. Но ничего страшного:

\[ 1027m=17n-17\cdot54+5 \]

\[ 1027m=17(n-54)+5 \]

\[ 1027m=17j+5,\quad j=n-54 \]

Дальше всё решается аналогично предыдущей задаче, надо будет только в конце учесть, что \(n=j+54\).