Une équation diophantienne est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières. Le terme est aussi utilisé pour les équations à coefficients rationnels. 

Le dixième problème de Hilbert

En 1900, Hilbert proposa la résolubilité de tous les problèmes diophantiens comme le dixième de ses célèbres problèmes. En 1970, un nouveau résultat en logique mathématique connu sous le nom de théorème de Yuri Matiyasevich le résolut négativement : en général les problèmes diophantiens ne sont pas résolubles, au sens où l'on peut construire explicitement de tels problèmes pour lesquels l'existence d'une solution est indécidable (dans le système axiomatique où l'on s'est placé ; on construit un polynôme précis en partant de la liste des axiomes).

Une équation diophantienne (à deux variables) est une équation de la forme générale :
 ax+by=c,
(1)

où  a, b, et c sont entiers. Ces équations peuvent être résolues et la première solution connue fut trouvée par Brahmagupta. 

Soit l'équation 

 ax+by=1.
(2)

Si l'on utilise une variation de l'algorithme d'Euclide, avec a=r_1 et 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 des dernières formules, l'on obtient :

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

donc

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)

On continue le procédé en remontant jusqu'en haut.

Par exemple, prenons l'équation : 

 1027x+712y=1
(11)

et appliquons l'algorithme précédent : 

  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 solution est donc x=-165, y=238.

La procédure précédente peut être simplifiée si l'on se penche sur les deux colonnes de gauche 

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)

donc les coefficients  r_(i-1) et r_(i+1) sont identiques et 

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

En reprenant l'exemple ci-dessus et en utilisant cette information, on trouve

  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)

et on retombe sur la solution précédente.

Soient x_0 et y_0 les solutions de

 ax+by=1
(18)

Si les signes devant ax ou by sont négatifs, alors, on résoud l'équation précédente et prend le signe des solutions du tableau qui suit :

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

En fait, la solution de l'équation 

 ax-by=1
(19)

revient à trouver la fraction continue pour a/b, avec a et b relativement premiers (Olds 1963). S'il existe n termes dans la fraction,  on prend  le (n-1)ème convergent vers p_(n-1)/q_(n-1). Mais

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

une solution est donc  x_0=(-1)^nq_(n-1), y_0=(-1)^np_(n-1), et la solution générale est : 

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

k est un nombre entier arbitraire.  

A présent, considérons l'équation générale de premier ordre 

 ax+by=c.
(23)

Le plus grand commun diviseur  d = PGCD (a,b) peut être trouvé grâce à la formule : 

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

a^'=a/d, b^'=b/d, et c^'=c/d. Si dc, alors c^' n'est pas un entier et l'équation ne peut pas avoir de solution dans N. Une condition nécessaire et suffisante pour que l'équation du premier ordre ait une solution dans N est donc que  d|c. Si c'est le cas, on peut résoudre 

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

et multiplier les solutions par c^', car

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

D. Wilson a réuni une liste des plus petites nièmes puissances d'entiers positifs qui sont les sommes des nièmes puissances d'entiers positifs distincts plus petits. Les premiers sont  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)