Une méthode d’Euler pour l’équation diophantienne du premier degré

Dans les éléments d'algèbre publiés par Euler en 1770, on trouve une intéressante méthode pour résoudre l'équation diophantienne du premier degré, c'est-à-dire l'équation : ax+by=cax + by = c en nombres entiers.

Résumé

Pour trouver les solutions xx, yy en nombres entiers à l’équation ax+by=cax + by = c avec aa, bb premiers entre eux, Euler a proposé (dans son livre Algèbre (1770), tome second, chap. 1) une démarche originale.

1 Description de la méthode

Considérons par exemple l’équation

39x+14y=10(1)\begin{aligned} 39x + 14y = 10 && (1)\\ \end{aligned}

Condition nécessaire

Supposons que xx, yy soit une solution en nombres entiers de cette équation.

Alors on peut exprimer yy en fonction de xx pour obtenir :

y=1039x14y = \dfrac{10 - 39x}{14}

c’est-à-dire, avec 39=2×14+1139 = 2 \times 14 + 11

y=1011x142x(2)\begin{aligned} y = \dfrac{10 - 11x}{14}-2x&& (2)\\ \end{aligned}

Du fait que xx et yy sont des nombres entiers, la quantité

p=1011x14p = \dfrac{10 - 11x}{14}

est aussi un nombre entier. On obtient donc, d’une part :
y=p2x(3)\begin{aligned} y = p-2x&& (3)\\ \end{aligned}

et d’autre part, xx et pp sont tels que :

14p+11x=10(4)\begin{aligned} 14p +11x= 10&& (4)\\ \end{aligned}

Ceci est une équation diophantienne du premier degré dont les coefficients sont globalement moindres que ceux de l’équation initiale.

On exprime alors xx en fonction de pp ; on obtient :

x=1014p11=103p11p(5)\begin{aligned} x = \dfrac{10 -14p}{11}= \dfrac{10 - 3p}{11}- p&& (5)\\ \end{aligned}

La quantité q=103p11q = \dfrac{10 -3p}{11} est un nombre entier ; on a donc

x=qp(6)\begin{aligned} x = q-p && (6)\\ \end{aligned}

qq et pp sont solutions de l’équation diophantienne

11q+3p=10(7)\begin{aligned} 11q +3p= 10 && (7)\\ \end{aligned}

Exprimant pp en fonction de qq, on obtient :

p=1011q3=12q3+33q(8)\begin{aligned} p = \dfrac{10-11q}{3} = \dfrac{1-2q}{3} +3 -3q && (8)\\ \end{aligned}

La quantité r=12q3r = \dfrac{1 - 2q}{3} est un nombre entier ; ceci permet d’écrire :

p=r+33q(9)\begin{aligned} p = r+3 - 3q && (9)\\ \end{aligned}

qq et rr sont solutions de l’équation diophantienne :

3r+2q=1(10)\begin{aligned} 3r + 2q = 1 && (10)\\ \end{aligned}

On exprime alors qq en fonction de rr ; ainsi :

q=13r2=1r2r(11)\begin{aligned} q = \dfrac{1 - 3r}{2} = \dfrac{1 - r}{2} - r && (11)\\ \end{aligned}

et en posant

s=1r2s = \dfrac{1 -r}{2}
qui est un nombre entier, on obtient :

q=sr(12)\begin{aligned} q = s - r && (12)\\ \end{aligned}

avec rr et ss liés par :
2s+r=1(13)\begin{aligned} 2s+r=1 && (13)\\ \end{aligned}

c’est-à-dire que l’on a :

r=12s(14)\begin{aligned} r=1-2s && (14)\\ \end{aligned}

On peut maintenant remonter cette suite de calculs.
On injecte l’expression de rr en fonction de ss donnée par (14)(14) dans l’égalité (12)(12), ce qui donne :

q=s(12s)=3s1(15)\begin{aligned} q = s-(1-2s) = 3s-1 && (15)\\ \end{aligned}

On peut donc remplacer rr et qq dans (9)(9) par leurs expressions en fonction de ss pour obtenir l’expression de pp en fonction de ss

p=(12s)+33(3s1)=711s(16)\begin{aligned} p = (1 - 2s) + 3 - 3(3s - 1) = 7 - 11s && (16)\\ \end{aligned}

et on peut ensuite remplacer p et q dans (6) pour obtenir l’expression de x en fonction de s

x=(3s1)(711s)=14s8(17)\begin{aligned} x = (3s - 1) - (7 - 11s) = 14s - 8 && (17)\\ \end{aligned}

Il reste alors à introduire cette expression ainsi que celle de pp dans (2)(2) pour obtenir :

y=(711s)2(14s8)=39s+23(18)\begin{aligned} y = (7 - 11s) - 2(14s - 8) = -39s + 23 && (18)\\ \end{aligned}

On a donc obtenu les expressions nécessaires des solutions xx et yy de l’équation (1)(1), s’il en existe, en fonction d’un paramètre entier ss.

Condition suffisante

Il suffit de vérifier qu’avec les expressions (17)(17) et (18)(18) on forme effectivement des solutions à l’équation (1)(1).

Or, on a : 39×(14s8)+14×(39s+23)=312+322=1039 \times (14s - 8) + 14 \times (-39s + 23) = -312 + 322 = 10.

Ceci montre que les solutions de l’équation diophantienne (1) sont exactement les nombres entiers de la forme
x=14s8ety=39s+23(19)\begin{aligned} x = 14s - 8 \\ et \\ y = -39s + 23 && (19)\\ \end{aligned}
pour tout ss entier relatif.

2 - Application pratique de la méthode

Concernant l’équation (d’après Continued fractions, Olds (1963)) diophantienne :

8x+5y=81(20)\begin{aligned} 8x + 5y = 81 && (20)\\ \end{aligned}

Voici une mise en œuvre plus rapide de ce procédé.

On commence avec :

y=818x5=13x5+16xy = \dfrac{81 - 8x}{5}= \dfrac{1 -3x}{5}+ 16 - x.

Avec p=13x5p = \dfrac{1 - 3x}{5}, on a :

y=p+16x,5p+3x=1(21)\begin{aligned} y = p + 16 - x, 5p + 3x = 1 && (21)\\ \end{aligned}

On exprime : x=15p3=12p3px = \dfrac{1 - 5p}{3}=\dfrac{1 -2p}{3}-p.

avec q=12p3q=\dfrac{1-2p}{3}, on a :

x=qp,3q+2p=1(22)\begin{aligned} x = q -p, 3q + 2p = 1 && (22)\\ \end{aligned}

On exprime

p=13q2=1q2qp=\dfrac{1-3q}{2} = \dfrac{1-q}{2}-q

Avec r=1q2r = \dfrac{1-q}{2}, on a :

p=rq,2r+q=1(23)\begin{aligned} p= r-q, 2r+q=1 && (23)\\ \end{aligned}

Ainsi on a : q=12rq = 1 -2r.

Alors, il vient : p=1(12r)=3r1p = 1 -(1 -2r) = 3r -1.

Ensuite :

x=(12r)(3r1)=25r(24)\begin{aligned} x = (1 -2r) -(3r -1) = 2 -5r && (24)\\ \end{aligned}

Enfin

y=(3r1)+16(25r)=13+8r(25)\begin{aligned} y= (3r -1) + 16 -(2 -5r) = 13 + 8r && (25)\\ \end{aligned}

On vérifie que :

8×(25r)+5×(13+8r)=16+65=818 \times(2 -5r) + 5 \times(13 + 8r) = 16 + 65 = 81.

Donc les solutions de l’équation (20)(20) sont exactement données par :

x=25r,y=13+8r\boxed{x = 2 -5r, y= 13 + 8r} (rr entier relatif)

Application.

De façon schématique, la méthode d’Euler pour résoudre ne équation diophantienne consiste :

  • d’abord à exprimer l’une des inconnues en fonction de l’autre,

  • puis à former une nouvelle équation diophantienne, dont les coefficients sont globalement inférieurs (en valeur absolue) à ceux de l’équation initiale.

L’inconnue à exprimer est celle dont le coefficient a la plus petite valeur absolue, le procédé devant être répété un certain nombre de fois.

Résoudre par cette méthode les équations diophantiennes suivantes :

  • 18x7y=5(26)\begin{aligned} 18x-7y=5&& (26)\\ \end{aligned}

  • 39x+25y=12(27)\begin{aligned} 39x+25y=12 && (27)\\ \end{aligned}

  • 20x+28y=100(28)\begin{aligned} 20x+28y=100 && (28)\\ \end{aligned}


Par Zauctore


Posez vos questions

D'autres interrogations sur ce cours ? Démarrez une discussion et obtenez des réponses à des exercices pratiques.

Accéder au forum


Progressez plus vite en maths

Boostez votre moyenne en mathématiques et découvrez les outils de soutien scolaire que nous avons sélectionné pour vous : cours particulier, chatbot, soutien scolaire... vous trouverez le service qui vous correspond !

Boostez votre moyenne