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 n=F_(2m)(onde F_(2m)é o (2m) Número de Fibonacci) é Diophantine. Mais especificamente, Matiyasevich mostraram que não é um polinómio Pin n, m, mas um número de outras variáveis x, y, z, ... tendo a propriedade que n=F_(2m) se existem inteiros x, y, z, ... de tal modo que P(n,m,x,y,z,...)=0.

Uma equação linear diofantina (em duas variáveis) é uma equação de forma geral

 ax+by=c,

(1)

Onde as soluções são procuradas com  a, b, e c inteiros. Estas equações podem ser resolvidas completamente, e a primeira solução conhecida foi calculada por Brahmagupta. Considere a equação

 ax+by=1.

(2)

Agora use uma variação do algoritmo de Euclides, deixando a=r_1e b=r_2

r_1

=

q_1r_2+r_3

(3)

r_2

=

q_2r_3+r_4

(4)

r_(n-3)

=

q_(n-3)r_(n-2)+r_(n-1)

(5)

r_(n-2)

=

q_(n-2)r_(n-1)+1.

(6)

A partir do fundo dá

1

=

r_(n-2)-q_(n-2)r_(n-1)

(7)

r_(n-1)

=

r_(n-3)-q_(n-3)r_(n-2),

(8)

assim

1

=

r_(n-2)-q_(n-2)(r_(n-3)-q_(n-3)r_(n-2))

(9)

=

-q_(n-2)r_(n-3)+(1+q_(n-2)q_(n-3))r_(n-2).

(10)

Continue este procedimento por todo o caminho e volte ao topo.

Tenha como exemplo a equação

 1027x+712y=1

(11)

E aplique o algoritmo acima, para obter

  1027 = 712·  1+  315;  712 = 315·  2+  82;  315 = 82·  3+  69;  82 = 69·  1+  13;  69 = 13·  5+  4;  13 = 4·  3+  1;    |; |; |; |; |; v;     1= -165·  1027+  238·  712; 1= 73·  712-  165·  315; 1= -19·  315+  73·  82; 1= 16·  82-  19·  69; 1= -3·  69+  16·  13; 1= 1·  13-  3·  4; 1= 0·  4+  1·  1^; |; |; |; |; |; |

(12)

A solução é, portanto x=-165, y=238.

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

1

=

-A_(i+1)r_i+A_ir_(i+1)

(13)

r_(i+1)

=

r_(i-1)-r_iq_(i-1)

(14)

1

=

A_ir_(i-1)-(A_iq_(i-1)+A_(i+1)),

(15)

De modo que os coeficientes de r_(i-1) e  r_(i+1) são os mesmos e

 A_(i-1)=-(A_iq_(i-1)+A_(i+1)).

(16)

Repetindo o exemplo acima usando esta informação, portanto dá

  1027 = 712·  1+  315;  712 = 315·  2+  82;  315 = 82·  3+  69;  82 = 69·  1+  13;  69 = 13·  5+  4;  13 = 4·  3+  1;    |; |; |; |; |; v;     (-)  165·  1+  73 = 238; (+)  73·  2+  19 = 165; (-)  19·  3+  16 = 73; (+)  16·  1+  3 = 19; (-)  3·  5+  1 = 16; (+)  1·  3+  0 = 3; (-)  0·  1+  1 = 1^; |; |; |; |; |; |

(17)

E recuperamos a solução acima.

Chame as soluções para

 ax+by=1

(18)

x_0e y_0. Se os sinais em frente  ax ou by são negativos, então resolva a equação de cima e tenha as indicações das soluções da seguinte tabela:

equação

x

y

ax+by=1

x_0

y_0

ax-by=1

x_0

-y_0

-ax+by=1

-x_0

y_0

-ax-by=1

-x_0

-y_0

De facto, a solução para a equação

 ax-by=1

(19)

É equivalente a encontrar a fracção continua para  a/b, com a e b relativamente primos (Olds 1963). Se houver  n termos da fracção, a tornar (n-1) o convergente p_(n-1)/q_(n-1). Mas

 p_nq_(n-1)-p_(n-1)q_n=(-1)^n,

(20)

Assim, uma solução é  x_0=(-1)^nq_(n-1), y_0=(-1)^np_(n-1), com uma solução geral

x

=

x_0+kb

(21)

y

=

y_0+ka

(22)

com k um número inteiro arbitrário. A solução, em termos de menores inteiros positivos é determinada pela escolha de uma adequada k.

Agora, considere a equação geral de primeira ordem da forma

 ax+by=c.

(23)

O maior divisor comum d=GCD(a,b) pode ser dividido cedendo

 a^'x+b^'y=c^',

(24)

onde a^'=a/d, b^'=b/d, e c^'=c/d. Se dc, então c^' 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  d|c. Se for este o caso, então resolva

 a^'x+b^'y=1

(25)

E multiplique as soluções por  c^', desde

 a^'(c^'x)+b^'(c^'y)=c^'.

(26)

D. Wilson compilou uma lista dos mais pequenos  n 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):

3^1

=

1^1+2^1

(27)

5^2

=

3^2+4^2

(28)

6^3

=

3^3+4^3+5^3

(29)

15^4

=

4^4+6^4+8^4+9^4+14^4

(30)

12^5

=

4^5+5^5+6^5+7^5+9^5+11^5

(31)

25^6

=

1^6+2^6+3^6+5^6+6^6+7^6+8^6+9^6+10^6+12^6+13^6+15^6+16^6+17^6+18^6+23^6

(32)

40^7

=

1^7+3^7+5^7+9^7+12^7+14^7+16^7+17^7+18^7+20^7+21^7+22^7+25^7+28^7+39^7

(33)

84^8

=

1^8+2^8+3^8+5^8+7^8+9^8+10^8+11^8+12^8+13^8+14^8+15^8+16^8+17^8+18^8+19^8+21^8+23^8+24^8+25^8+26^8+27^8+29^8+32^8+33^8+35^8+37^8+38^8+39^8+41^8+42^8+43^8+45^8+46^8+47^8+48^8+49^8+51^8+52^8+53^8+57^8+58^8+59^8+61^8+63^8+69^8+73^8

(34)

47^9

=

1^9+2^9+4^9+7^9+11^9+14^9+15^9+18^9+26^9+27^9+30^9+31^9+32^9+33^9+36^9+38^9+39^9+43^9

(35)

63^(10)

=

1^(10)+2^(10)+4^(10)+5^(10)+6^(10)+8^(10)+12^(10)+15^(10)+16^(10)+17^(10)+20^(10)+21^(10)+25^(10)+26^(10)+27^(10)+28^(10)+30^(10)+36^(10)+37^(10)+38^(10)+40^(10)+51^(10)+62^(10).

(36)