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

Диофа́нтово уравнение — это уравнение вида

$P(x_1, \dots, x_m) = 0,$

где P — целочисленная функция (например, полином с целыми коэффициентами), а переменные $x_i$ принимают целые значения. Названы в честь древнегреческого математика Диофанта.

Примеры

• $x^n + y^n = z^n$:
  • При $n=2$ решениями этого уравнения являются пифагоровы тройки.
  • Великая теорема Ферма утверждает, что это уравнение не имеет положительных целых решений при $n>2$.
• $\sum\limits_{k=1}^{n-1} a_k^n = a_n^n$ — гипотеза Эйлера утверждает, что для любого натурального числа n > 2 это уравнение неразрешимо в натуральных числах $a_1, a_2, \dots, a_n$, то есть, никакую n-ю степень натурального числа нельзя представить в виде суммы n-1 n-х степеней других натуральных чисел. Гипотеза является обобщением великой теоремы Ферма, но была опровергнута для n = 4 и n = 5.
• $x^2 - n y^2 = 1$, где параметр n не является точным квадратом — уравнение Пелля.
• $x^z - y^t = 1$, где $z, t>1$, — уравнение Каталана.
• $\sum_{i=0}^n a_i x^i y^{n-i} = c$ при $n\ge 3$ и $c\ne 0$ — уравнение Туэ.

Алгебраические диофантовы уравнения

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

Также, при рассмотрении вопроса разрешимости переменные часто разделяют на параметры (значения которых предполагаются фиксированными) и неизвестные. Таким образом, каждое диофантово уравнение определяет множество наборов параметров, при которых оно разрешимо относительно неизвестных, называемое диофантовым множеством. Рассматриваемое диофантово уравнение называется диофантовым представлением этого множества. Важный результат, полученный Юрием Матиясевичем, состоит в том, что каждое перечислимое множество имеет диофантово представление.

Линейные диофантовы уравнения

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

$a_1 x_1 + a_2 x_2 + \ldots + a_k x_k=d.$

В частности, линейное диофантово уравнение с двумя неизвестными имеет вид:

$ax+by=c.\qquad(1)$

Если $(a,b) \nmid c$ (то есть $c$ не делится нацело на наибольший общий делитель $(a,\;b)$), то уравнение (1) не разрешимо в целых числах. В самом деле, если $(a,\;b) \ne 1$, то число, стоящее слева в (1), делится на $(a,\;b)$, а стоящее справа — нет. Справедливо и обратное: если в уравнении $ax+by=c$ выполняется $(a,b) \mid c$, то оно разрешимо в целых числах.

Пусть $(x_0,\;y_0)$ — частное решение уравнения $ax+by=c$. Тогда все его решения находятся по формулам:

$\begin{cases} x=x_0-\frac{b}{(a,\;b)}n \\ y=y_0+\frac{a}{(a,\;b)}n\end{cases}\quad n \in\mathbb Z.$

Частное решение $(x_0,\;y_0)$ можно построить следующим образом. Если $(a, b)\ne 1$ и c делится на $(a,b)$, то после деления всех коэффициентов на $(a,b)$ уравнение приобретает вид $a_1x+b_1y = c_1$, где $(a_1,b_1)=1$. Для последнего уравнения частное решение получается из соотношения Безу для a₁, b₁:

$u a_1 + v b_1 = 1,$

исходя из которого, можно положить $(x_0,\;y_0) = (c_1\cdot u,\;c_1\cdot v).$

Известна явная формула для серии решений линейного уравнения:

$\begin{cases}x_t=c a^{\phi(b)-1}+b t,\\ y_t=c\frac{1-a^{\phi(b)}}{b}-a t,\end{cases}$

где $\phi(\cdot)$ — функция Эйлера, а t — произвольный целый параметр.

Неразрешимость в общем виде

Десятая проблема Гильберта, сформулированная в 1900 году, состоит в нахождении алгоритма решения произвольных алгебраических диофантовых уравнений. В 1970 году Юрий Матиясевич доказал алгоритмическую неразрешимость этой проблемы.

См. также

• Решение сравнений

Ссылки

• Гельфонд А.О. Решение уравнений в целых числах. — М.: Наука, 1978. — (Популярные лекции по математике).
• В. Н. Серпинский О решении уравнений в целых числах. — М.: Физматлит, 1961. — 88 с.
• И. Михайлов О диофантовом анализе // Квант. — 1980. — № 6. — С. 16-17,35.
• С. А. Степанов Диофантовы уравнения // Тр. МИАН СССР. — 1984. — Т. 168. — С. 31–45.
• Weisstein, Eric W. Diophantine Equation (англ.) на сайте Wolfram MathWorld.