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

Диофа́нтово уравнение или уравнение в целых числах — это уравнение с целыми коэффициентами и неизвестными, которые могут принимать только целые значения. Названы в честь древнегреческого математика Диофанта.

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

Общий вид линейного диофантова уравнения: $ax+by+\ldots+cz=d$. В литературе под диофантовыми уравнениями иногда понимаются также уравнения более частного вида — с двумя неизвестными:

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

которые достаточно хорошо изучены.

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

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

x = x₀ − bn, y = y₀ + an, $n \in\mathbb Z$.

Начальное (базисное) решение $(x_0,\;y_0)$ можно построить таким образом. Если $(a, b) \ne 1$, то (если уравнение имеет решения) c делится на (a, b) в силу вышесказанного. Тогда уравнение сводится к виду a₁x + b₁y = c₁ путем деления всех коэффициентов на (a,b). Для уравнения ax + by = c с (a,b) = 1 базисное решение получается из соотношения Безу для a, b:

ua + vb = 1,

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

Некоторые другие уравнения

• xⁿ + yⁿ = zⁿ:
  • При n = 2 решениями этого уравнения являются пифагоровы тройки
  • Великая теорема Ферма утверждает, что это уравнение не имеет положительных целых решений при n > 2.
• x² − ny² = 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$ — уравнения Туэ

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

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

См. также

• Гельфонд А.О. Решение уравнений в целых числах. — М.: Наука, 1978. — (Популярные лекции по математике).
• В. Н. Серпинский О решении уравнений в целых числах. — М.: Физматлит, 1961. — 88 с.