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

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

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

Содержание

1 Линейные диофантовы уравнения
- 1.1 Способ решения
2 Некоторые другие уравнения
3 Неразрешимость в общем виде
4 См. также

[править] Линейные диофантовы уравнения

Общий вид линейного диофантова уравнения: $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)$ , а стоящее справа — нет. Если в уравнении $a x + b y = 1$ $(a,\;b)=1$ , то оно разрешимо в целых числах.

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

x = x 0 - b n

y = y 0 + a n

, $n \in\mathbb Z$ .

[править] Способ решения

Эту статью следует викифицировать.

Пожалуйста, оформите её согласно правилам оформления статей.

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

$ax+by=1;\qquad(1.1)$

решение же уравнения (1) получим просто домножением корней на c. Уравнение 1.1 решается таким образом. Строим цепочку делений с остатком (как при поиске наибольшего общего делителя с помощью алгоритма Евклида):

a = b q 0 + r 1

b = r 1 q 1 + r 2

r 1 = r 2 q 2 + r 3

$\cdots$

r n - 1 = r n q n

Последний ненулевой остаток $r n$ равен 1, т. к. (a, b) = 1. Теперь заметим, что каждый остаток можно представить в виде

r i + 1 = r i - 1 - r i q i

в частности,

1 = r n - 2 - r n - 1 q n - 1

Выражая теперь каждый следующий остаток через два предыдущих ("поднимаясь" по цепочке делений), придем к выражению вида

1 = αa + βb,

где α и β - корни уравнения (1.1). Домножая их на c, получим корни x₀ = αc, y₀ = βc уравнения (1).

Пример.

86 x + 30 y = 14

Приводится к виду

43 x + 15 y = 7

Цепочка делений

43/15 = 2 (ост. 13)

15/13 = 1 (ост. 2)

13/2 = 6 (ост. 1)

1 = 13 - 2·6= 13 - (15-13)·6 = 13·7 - 15·6 = (43-2·15)·7 - 15·6 = 43·7 - 20·15,

умножая 7 и -20 на c (=7), получаем корни 49 и -140.

Общий вид всех корней

x = 49 + 15 n

y = - 140 - 43 n

[править] Некоторые другие уравнения

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