Диофантово уравнение

Пусть ${\displaystyle P}$ — полином от ${\displaystyle m}$ переменных с целыми коэффициентами. Целочисленным решением уравнения ${\displaystyle P(x_{1},\dots ,x_{m})=0}$ называется набор целых чисел ${\displaystyle (x_{1},\dots ,x_{m})}$, при подстановке которого равенство обращается в истину; уравнение называется разрешимым, если оно имеет хотя бы одно целочисленное решение^[13][14]. Вместо целых решений могут рассматриваться натуральные (тогда говорят о разрешимости в натуральных числах) или рациональные — последнее обычно является существенно более трудной задачей, связанной с эллиптическими кривыми^[3]. Заметим, что разрешимость в целых числах эквивалентна разрешимости в натуральных: всякое целое число представимо как разность двух натуральных, а требование неотрицательности переменной ${\displaystyle x}$ выражается, по теореме Лагранжа о четырёх квадратах, заменой ${\displaystyle x=(u_{1}^{2}+u_{2}^{2}+u_{3}^{2}+u_{4}^{2})-(v_{1}^{2}+v_{2}^{2}+v_{3}^{2}+v_{4}^{2})}$^[4].

При исследовании разрешимости переменные часто делят на параметры ${\displaystyle a_{1},\dots ,a_{n}}$ (их значения считаются заданными) и неизвестные ${\displaystyle x_{1},\dots ,x_{m}}$: уравнение ${\displaystyle P(a_{1},\dots ,a_{n},x_{1},\dots ,x_{m})=0}$ разрешимо при данном наборе параметров, если существует набор неизвестных, обращающий равенство в истину^[4]. Множество наборов параметров, при которых уравнение разрешимо, называется диофантовым множеством; само уравнение при этом называется его диофантовым представлением^[15].

• ${\displaystyle x^{2}+y^{2}=z^{2}}$ — уравнение, целые решения которого образуют пифагоровы тройки; при ${\displaystyle n=2}$ это частный случай уравнения Ферма, имеющий бесконечно много решений^[16].
• ${\displaystyle x^{n}+y^{n}=z^{n}}$, ${\displaystyle n>2}$ — согласно Великой теореме Ферма, доказанной Э. Уайлсом в 1995 году, не имеет ненулевых целых решений^[17].
• ${\displaystyle \sum _{k=1}^{n-1}a_{k}^{n}=a_{n}^{n}}$ — гипотеза Эйлера утверждала неразрешимость этого уравнения в натуральных числах при ${\displaystyle n>2}$; она опровергнута: при ${\displaystyle n=5}$ контрпример ${\displaystyle 27^{5}+84^{5}+110^{5}+133^{5}=144^{5}}$ найден Ландером и Паркиным (1966)^[18], при ${\displaystyle n=4}$ — Элкисом (1986)^[19]; уточняющая гипотеза Ландера — Паркина — Селфриджа остаётся открытой.
• ${\displaystyle x^{2}-ny^{2}=1}$, где ${\displaystyle n}$ — не точный квадрат, — уравнение Пелля; имеет бесконечно много целых решений.
• ${\displaystyle x^{z}-y^{t}=1}$, ${\displaystyle z,t>1}$ — уравнение Каталана, единственное решение которого ${\displaystyle 3^{2}-2^{3}=1}$ доказано Михайлеску (2002)^[20].
• ${\displaystyle \sum _{i=0}^{n}a_{i}x^{i}y^{n-i}=c}$ при ${\displaystyle n\geq 3}$, ${\displaystyle c\neq 0}$ — уравнение Туэ; имеет лишь конечное число целых решений (А. Туэ, 1909)^[12].

Общий вид линейного диофантова уравнения:

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{k}x_{k}=d;}$

оно разрешимо в целых числах тогда и только тогда, когда наибольший общий делитель ${\displaystyle (a_{1},\dots ,a_{k})}$ делит ${\displaystyle d}$. Основной случай — уравнение с двумя неизвестными:

${\displaystyle ax+by=c,\qquad (1)}$

где ${\displaystyle a,b}$ — целые, не равные нулю одновременно^[21][22].

Теорема (критерий разрешимости и общий вид решений). Пусть ${\displaystyle d=(a,b)}$. Уравнение (1) разрешимо в целых числах тогда и только тогда, когда ${\displaystyle d\mid c}$. В этом случае, если ${\displaystyle (x_{0},y_{0})}$ — какое-либо частное решение, то множество всех решений исчерпывается парами

${\displaystyle x=x_{0}+{\frac {b}{d}}\,t,\qquad y=y_{0}-{\frac {a}{d}}\,t,\qquad t\in \mathbb {Z} .}$

Доказательство. Необходимость. Поскольку ${\displaystyle d\mid a}$ и ${\displaystyle d\mid b}$, число ${\displaystyle ax+by}$ делится на ${\displaystyle d}$ при любых целых ${\displaystyle x,y}$; следовательно, из ${\displaystyle ax+by=c}$ следует ${\displaystyle d\mid c}$. Достаточность, случай ${\displaystyle (a,b)=1}$. По соотношению Безу (получаемому, например, алгоритмом Евклида) существуют целые ${\displaystyle u,v}$, для которых ${\displaystyle ua+vb=1}$; тогда ${\displaystyle (x_{0},y_{0})=(cu,cv)}$ — решение уравнения (1). Достаточность, общий случай. Если ${\displaystyle d\mid c}$, то делением (1) на ${\displaystyle d}$ получаем уравнение ${\displaystyle a_{1}x+b_{1}y=c_{1}}$ с ${\displaystyle (a_{1},b_{1})=1}$, к которому применим предыдущий случай. Описание всех решений. Пусть ${\displaystyle (x,y)}$ — произвольное решение; вычитая ${\displaystyle ax_{0}+by_{0}=c}$, получаем ${\displaystyle a(x-x_{0})+b(y-y_{0})=0}$, откуда ${\displaystyle {\frac {a}{d}}(x-x_{0})=-{\frac {b}{d}}(y-y_{0})}$. Так как ${\displaystyle \left({\frac {a}{d}},{\frac {b}{d}}\right)=1}$, по лемме Гаусса ${\displaystyle {\frac {b}{d}}\mid (x-x_{0})}$, то есть ${\displaystyle x-x_{0}={\frac {b}{d}}t}$ для некоторого ${\displaystyle t\in \mathbb {Z} }$; подстановка в последнее равенство даёт ${\displaystyle y-y_{0}=-{\frac {a}{d}}t}$. Обратно, подстановка любой пары такого вида в (1) обращает его в истину, откуда следует, что полученные формулы исчерпывают все решения. ${\displaystyle \blacksquare }$

Частное решение практически находится расширенным алгоритмом Евклида; разложение в цепную дробь отношения ${\displaystyle a/b}$ даёт его также через подходящие дроби^[23][24]. Существует и явная, хотя и неэффективная для вычислений, формула частной серии решений через функцию Эйлера: по теореме Эйлера ${\displaystyle a^{\varphi (|b|)}\equiv 1{\pmod {|b|}}}$ при ${\displaystyle (a,b)=1}$, откуда

${\displaystyle x_{t}=c\,a^{\varphi (|b|)-1}+bt,\qquad y_{t}=c\,{\frac {1-a^{\varphi (|b|)}}{b}}-at,\qquad t\in \mathbb {Z} ,}$

— всегда целая серия решений уравнения ${\displaystyle ax+by=c}$^[23][25][26].

Если неизвестные входят в показатели степеней, уравнение называется экспоненциальным диофантовым. Примеры:

• Уравнение Рамануджана — Нагеля ${\displaystyle 2^{n}-7=x^{2}}$: имеет ровно пять решений — ${\displaystyle (x,n)\in \{(1,3),(3,4),(5,5),(11,7),(181,15)\}}$ (доказано Т. Нагеллем в 1948 году)^[35][36];
• уравнение Каталана ${\displaystyle x^{a}-y^{b}=1}$ (решено Михайлеску, 2002)^[20];
• уравнения гипотезы Ферма — Каталана и гипотеза Била, остающиеся открытыми.

Общей теории решения экспоненциальных уравнений не существует; тем не менее отдельные классы поддаются специальным методам: теорема Стёрмера о последовательных «гладких» числах решает целые семейства таких уравнений, а метод Бейкера (линейные формы от логарифмов алгебраических чисел) даёт для широкого класса уравнений эффективные верхние оценки неизвестных, после чего задача сводится к конечному — хотя зачастую и очень большому — перебору, выполняемому с помощью компьютера^[29][30].

Десятая проблема Гильберта, сформулированная в 1900 году, требовала общего алгоритма, решающего, разрешимо ли произвольное диофантово уравнение в целых числах. Работа М. Дэвиса, Х. Патнема и Дж. Робинсон над экспоненциальными уравнениями^[37] была завершена Ю. В. Матиясевичем (1970): каждое перечислимое множество является диофантовым, а поскольку существуют перечислимые неразрешимые множества, требуемого алгоритма не существует^[4]. Неразрешимость сохраняется уже для уравнений с 9 неизвестными и для уравнений степени 4^[4][34]. Вопросы о разрешимости отдельных классов (например, уравнений третьей степени или уравнений над полем рациональных чисел) остаются открытыми.

• Криптография. Нахождение секретного ключа в системе RSA есть решение линейного сравнения ${\displaystyle ed\equiv 1{\pmod {\varphi (n)}}}$, то есть линейного диофантова уравнения, расширенным алгоритмом Евклида^[38]; криптосистема Меркле — Хеллмана основана на «задаче о ранце» — системе линейных уравнений в целых числах^[39].
• Программирование и оптимизация. Критерий разрешимости линейных диофантовых уравнений (GCD-тест) применяется при анализе зависимостей по данным в автоматической параллелизации программ^[40]; поиск целочисленных решений линейных систем составляет предмет целочисленного программирования (задачи расписаний, транспортировки).
• Химия. Подбор коэффициентов химического уравнения — задача о решении системы линейных диофантовых уравнений; алгоритмы уравнивания реакций прямо используют строение решётки целых решений^[11].
• Экономика и комбинаторика. «Задача о размене» (монеты Фробениуса) — классическая диофантова задача о наибольшей сумме, не представимой данным набором номиналов^[41].
• Теория чисел и образование. Диофантовы уравнения — традиционный материал олимпиадных задач и учебных курсов элементарной теории чисел^[23].