Un'equazione diofantea è un'equazione in cui sono ammesse solo soluzioni intere.

Il 10° problema di Hilbert si chiedeva se esiste un algoritmo per determinare se un'equazione diofantea arbitraria ha una soluzione. Un tale algoritmo non esiste per la soluzione di equazioni diofantee di primo ordine. Tuttavia, l'impossibilità di ottenere una soluzione generale è stata dimostrata da Yuri Matiyasevich nel 1970 (Matiyasevich 1970, Davis 1973, Davis e Hersh 1973, Davis 1982, Matiyasevich 1993) dimostrando che la relazione n=F_(2m) (dove F_(2m) è il(2m)numero di Fibonacci) è diofantea. Più specificamente, Matiyasevich ha dimostrato che esiste un polinomioP in n, m, e altre variabili x, y, z, ... che hanno la proprietà di n=F_(2m) se e solo se esistono degli interi x, y, z, ... tali che P(n,m,x,y,z,...)=0.

I risultati di Matiyasevich riempirono un vuoto cruciale nel precedente lavoro di Martin Davis, Hilary Putnam, e Julia Robinson. I lavori successivi di Matiyasevich e Robinson dimostrarono che anche per le equazioni a tredici variabili, non può esistere alcun algoritmo per determinare se c'è una soluzione. Matiyasevich ha poi migliorato questo risultato per le equazioni a nove variabili (Jones e Matiyasevich 1982).

Ogilvy e Anderson (1988) fornirono un numero di equazioni diofantee con soluzioni conosciute e sconosciute.

Un'equazione lineare diofantea (in due variabili) è un'equazione della forma:

 ax+by=c,
(1)

in cui le soluzioni si cercano con a, b, e c interi. Tali equazioni possono essere risolti completamente, e la prima soluzione nota è stato costruito da Brahmagupta. Consideriamo l'equazione

 ax+by=1.
(2)

Ora usiamo una variazione dell'algoritmo euclideo, lasciando a=r_1 e 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)

Partendo dal basso si ha

1=r_(n-2)-q_(n-2)r_(n-1)
(7)
r_(n-1)=r_(n-3)-q_(n-3)r_(n-2),
(8)

quindi

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)

Continuare questa procedura fino alla fine verso l'alto.

Prendiamo come esempio l'equazione

 1027x+712y=1
(11)

e applicare l'algoritmo sopra per ottenere

  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)

La soluzione è pertanto x=-165, y=238.

La procedura sopra descritta può essere semplificata notando che le due colonne più a sinistra sono compensate da una entry e segni alterni, come è necessario poiché

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)

quindi i coefficienti di r_(i-1) and r_(i+1) sono gli stessi e

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

Ripetendo l'esempio precedente utilizzando queste informazioni, dunque

  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 si recupera la soluzione sopra.

Chiamiamo le soluzioni di

 ax+by=1
(18)

x_0 e y_0. Se i segni davanti a ax o by sono negativi, quindi risolvere l'equazione qui sopra e prendere i segni delle soluzioni dalla tabella seguente:

equazionexy
ax+by=1x_0y_0
ax-by=1x_0-y_0
-ax+by=1-x_0y_0
-ax-by=1-x_0-y_0

Infatti la soluzione dell'equazione

 ax-by=1
(19)

è equivalente a trovare la frazione continua per a/b, con a e b coprimi (Olds 1963). Se ci sono n termini nella frazione, prendere i (n-1)convergnti p_(n-1)/q_(n-1). Ma

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

così una soluzione è x_0=(-1)^nq_(n-1), y_0=(-1)^np_(n-1), con una soluzione generale

x=x_0+kb
(21)
y=y_0+ka
(22)

con k un intero. La soluzione in termini di piccoli interi positivi è data dalla scelta di un appropriato k.

Ora consideriamo l' equazione generale della forma

 ax+by=c.
(23)

Il massimo comun divisore d=GCD(a,b) può essere diviso ottenendo

 a^'x+b^'y=c^',
(24)

dove a^'=a/d, b^'=b/d, e c^'=c/d. Se dc, allora c^' non è un intero e l'equazione non può avere una soluzione in numeri interi. Una condizione necessaria e sufficiente per l'equazione generale di avere soluzioni in numeri interi è pertanto d|c. Se questo è il caso, allora risolvere

 a^'x+b^'y=1
(25)

e moltiplicare le soluzioni per c^', poichè

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

D. Wilson ha compilato una lista delle n potenze più piccole di interi positivi che sono la somma di n potenze distinte di piccoli interi positivi. Le prime sono 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)