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

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

Примеры



  • xn+yn=zn:
    • При n=2 решениями этого уравнения являются пифагоровы тройки.
    • согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при n>2.

  • k=1n1akn=ann — гипотеза Эйлера утверждает, что для любого натурального числа n \textgreater 2 это уравнение неразрешимо в натуральных числах a1,a2,,an, то есть, никакую n-ю степень натурального числа нельзя представить в виде суммы n-1 n-х степеней других натуральных чисел. Гипотеза является обобщением великой теоремы Ферма, но была опровергнута для n = 4 и n = 5.
  • x2ny2=1, где параметр n не является точным квадратом — уравнение Пелля.
  • xzyt=1, где z,t>1, — уравнение Каталана.
  • i=0naixiyni=c при n3 и c0 — уравнение Туэ.

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


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

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


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

a1x1+a2x2++akxk=d.
 В частности, линейное диофантово уравнение с двумя неизвестными имеетвид:

ax+by=c.(1)
 Если (a,b)c (то есть наибольший общий делитель (a,b) неделит c), то уравнение (1) не разрешимо в целых числах. В самом деле,если (a,b)1, то число, стоящее слева в (1), делится на(a,b), а стоящее справа — нет. Справедливо и обратное: если вуравнении ax+by=c выполняется (a,b)c, то оно разрешимо в целыхчислах.
 Пусть (x0,y0) — частное решение уравнения ax+by=c. Тогда всеего решения находятся по формулам:

{x=x0+nb(a,b)y=y0na(a,b)nZ.
 Частное решение (x0,y0) можно построить следующим образом. Если(a,b)1 и c делится на (a,b), то после деления всехкоэффициентов на (a,b) уравнение приобретает вид a1x+b1y=c1,где (a1,b1)=1. Для последнего уравнения частное решение получаетсяиз соотношения Безу для a1,b1:

ua1+vb1=1,
 исходя из которого, можно положить(x0,y0)=(c1u,c1v).
 Известна явная формула для серии решений линейного уравнения:

{xt=caφ(b)1+bt,yt=c1aφ(b)bat,
 где φ() — функция Эйлера, а t — произвольныйцелый параметр.

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


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