Глава 33. Диофантовы уравнения

Эта глава продолжает тему, затронутую в главе 32. «Поиск простых чисел с помощью регулярных выражений» — применение регулярных выражений в задачах, связанных с целочисленной делимостью.

Речь пойдёт о линейных диофантовых уравнениях.

Диофантово уравнение — это уравнение (как правило, с несколькими неизвестными), решение которого ищется в целых (иногда в натуральных) числах. Классическим диофантовым уравнением является уравнение Ферма: $$x^n+y^n=z^n\text{.}$$ Неизвестными в нём являются четыре натуральных переменных $x$, $y$, $z$, $n$.

Недавно доказанная теорема Ферма утверждает, что при $n>2$ уравнение Ферма неразрешимо в натуральных числах. Доказать эту теорему было очень, очень непросто. Кроме того, хорошо известно, что при $n=2$ уравнение разрешимо, и ещё как! Бесконечно много троек натуральных чисел $\left(x,y,z\right)$ обращают уравнение в верное равенство. Две наиболее известных из них — это пифагоровы тройки $\left(3,4,5\right)$ (катеты и гипотенуза египетского прямоугольного треугольника) и $\left(5,12,13\right)$.

Нас же сейчас интересуют линейные диофантовы уравнения, то есть такие, в которых все переменные входят линейным образом: $$a_1{x}_1+a_2{x}_2+a_3{x}_3+\dots +a_n{x}_n=b\text{.}$$ Неизвестными здесь служат буквы $x_i$, $i=1,\dots ,n$, а целые числа $a_i$ и $b$ заданы свыше.

Рисунок 33.1. Решение линейных диофантовых уравнений с двумя неизвестными (страницы из брошюры [24])

Читатели, интересующиеся математической стороной вопроса, могут ознакомиться с двумя методами решения линейных диофантовых уравнений с двумя неизвестными по винтажной шпаргалке [24] 1924 года издания (рисунок 33.1); там такие уравнения называются неопределёнными. Качество печати оставляет желать лучшего. Формулу (1) на странице 31 следует читать как $ax+by=c$.

Особенностью обсуждаемого в этой главе алгоритма является то, что он может находить лишь одно из решений уравнений такого типа, причём каждое из чисел $a_i$, $b$ должно быть неотрицательным целым. Кроме того, все найденные $x_i$ могут быть целыми неотрицательными.

Такого рода задачи возникают, например, в связи с разменом денег. Например: как разменять $37$ рублей монетами достоинством в $5$ и $11$ рублей (допустим, что такие монеты бывают). Такая задача приводит к уравнению $5x+11y=37$. Его единственное решение в натуральных числах — это $x=3$, $y=2$. Очевидно, другие подобные задачи о размене могут иметь более одного решения.

Напишем программу diophantus.pl, получающую в командной строке числа $a_i$ и $b$, и выводящую целое неотрицательное решение линейного диофантова уравнения, если оно есть. Если такого решения нет, выводится сообщение об этом:

% ./diophantus.pl 5 11 37
3 2
% ./diophantus.pl 19 6 11 3 2 51
2 1 0 1 2
% ./diophantus.pl 6 11 37
./diophantus.pl: Не могу решить уравнение!