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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править исходный текст]

  • x^n + y^n = z^n:
  • \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 (то есть наибольший общий делитель (a,\;b) не делит c), то уравнение (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. Для последнего уравнения частное решение получается из соотношения Безу для a1, b1:

u a_1 + v b_1 = 1,

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

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

\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 году Юрий Матиясевич доказал алгоритмическую неразрешимость этой проблемы.[2]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Воробьёв Н. Н. Признаки делимости. — М.: Наука, 1988. — С. 60. — 96 с. — (Популярные лекции по математике).
  2. Ю. В. Матиясевич Десятая проблема Гильберта. — М.: Наука, 1993.

Ссылки[править | править исходный текст]