A equação diofantina é uma equação
em que apenas soluções inteiras são permitidas.
O 10º problema de Hilbert perguntou
se existia um algoritmo para determinar se uma equação diofantina arbitrária
tem solução. Tal algoritmo existe para a solução das equações diofantinas de
primeira ordem. No entanto, a impossibilidade de se obter uma solução geral foi
comprovada por Yuri Matiyasevich in 1970 (Matiyasevich 1970, Davis 1973, Davis
and Hersh 1973, Davis 1982, Matiyasevich 1993) mostrando que a relação (onde
é o
Número de Fibonacci)
é Diophantine. Mais especificamente, Matiyasevich mostraram que não é um
polinómio
in
,
, mas um número de outras variáveis
,
,
, ... tendo a propriedade que
se existem inteiros
,
,
, ... de tal modo que
.
Uma equação linear diofantina (em
duas variáveis) é uma equação de forma geral
|
(1)
|
Onde as soluções são procuradas com ,
, e
inteiros. Estas
equações podem ser resolvidas completamente, e a primeira solução conhecida foi
calculada por Brahmagupta. Considere a equação
|
(2)
|
Agora use uma variação do algoritmo
de Euclides, deixando e
|
|
|
(3)
|
|
|
|
(4)
|
|
|
|
(5)
|
|
|
|
(6)
|
A partir do fundo dá
|
|
|
(7)
|
|
|
|
(8)
|
assim
|
|
|
(9)
|
|
|
|
(10)
|
Continue este procedimento por todo
o caminho e volte ao topo.
Tenha como
exemplo a equação
|
(11)
|
E aplique o algoritmo acima, para
obter
|
(12)
|
A solução é, portanto ,
.
O procedimento acima pode ser
simplicado fazendo notar que as colunas mais à esquerda são compensadas por uma
entrada e sinais alternados, como devem ser
|
|
|
(13)
|
|
|
|
(14)
|
|
|
|
(15)
|
De modo que os coeficientes de e
são os mesmos e
|
(16)
|
Repetindo o exemplo acima usando
esta informação, portanto dá
|
(17)
|
E recuperamos a solução acima.
Chame as soluções para
|
(18)
|
e
. Se os sinais em frente
ou
são negativos, então
resolva a equação de cima e tenha as indicações das soluções da seguinte tabela:
equação |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
De facto, a solução para a equação
|
(19)
|
É equivalente a encontrar a fracção
continua para , com
e
relativamente primos
(Olds 1963). Se houver
termos da fracção, a
tornar
o convergente
. Mas
|
(20)
|
Assim, uma solução é ,
, com uma solução geral
|
|
|
(21)
|
|
|
|
(22)
|
com um número inteiro
arbitrário. A solução, em termos de menores inteiros positivos é determinada
pela escolha de uma adequada
.
Agora, considere a equação geral de
primeira ordem da forma
|
(23) |
O maior divisor comum pode
ser dividido cedendo
|
(24)
|
onde ,
, e
. Se
, então
não é um número
inteiro e a equação não pode ter uma solução em números inteiros. Uma condição
necessária é suficiente para a equação geral de primeira ordem para ter as
soluções com base em números é, por conseguinte, que
. Se for este o caso, então resolva
|
(25)
|
E multiplique as soluções por , desde
|
(26)
|
D. Wilson compilou uma lista
dos mais pequenos os poderes de
inteiros positivos que são as somas dos poderes de distintas inteiros positivos
menores. Os primeiros são 3, 5, 6, 15, 12, 25, 40, ...(Sloane's A030052):
|
|
|
(27)
|
|
|
|
(28)
|
|
|
|
(29)
|
|
|
|
(30)
|
|
|
|
(31)
|
|
|
|
(32)
|
|
|
|
(33)
|
|
|
|
(34)
|
|
|
|
(35)
|
|
|
|
(36)
|