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

Постановка задачи

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

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

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

Мы бы с удовольствием привели доказательство теоремы Ферма, но поля слишком малы…

⁂ ⁂ ⁂ ⁂ ⁂ ⁂ ⁂ ⁂ ⁂ ⁂
ДОКАЗАЛ ТЕОРЕМУ ФЕРМА ТЧК ИКС СТЕПЕНИ Н ПЛЮС ИГРЕК СТЕПЕНИ Н РАВНО ЗЕТ СТЕПЕНИ Н ТЧК ДОКАЗАТЕЛЬСТВО ДВТЧ ПЕРЕНОСИМ ИГРЕК СТЕПЕНИ Н ПРАВУЮ ЧАСТЬ ТЧК ПОДРОБНОСТИ ПИСЬМОМ ТЧК

Телеграмма в академию наук

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

Нас же сейчас интересуют линейные диофантовы уравнения, то есть такие, в которых все переменные входят линейным образом: $a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} + \dots + a_{n} x_{n} = b .$ Неизвестными здесь служат буквы $x_{i}$ , $i = 1, \dots, n$ , а целые числа $a_{i}$ и $b$ заданы свыше.

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

Нас очень растрогало выражение «выносить общего множителя».

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

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

Такого рода задачи возникают, например, в связи с разменом денег. Например: как разменять $37$ рублей монетами достоинством в $5$ и $11$ рублей (допустим, что такие монеты бывают). Такая задача приводит к уравнению $5 x + 11 y = 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: Не могу решить уравнение!


Готовая программа		Идеи реализации