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


Cours de mathématiques Hors Programme

  1. Définitions de réciproque, contraposée, démonstration par l'absurde et algorithme
  2. Équation de Fermat pour p égal à 3
  3. Précision sur le théorème de Fermat-Euler
  4. Méthode de Horner (ou schéma de Horner)
  5. LaTeX: Dessin géométrique en LaTeX avec PSTricks
  6. Inégalités et Encadrements
  7. Équation diophantienne à la façon d'Euler
  8. Sommes de carrés : un théorème d'Aubry
  9. Développements limités
  10. Groupes finis et groupes cycliques
  11. Entiers d'Eisenstein
  12. Comment prendre des cours de maths en ligne ?
  13. 4 bonnes raisons de prendre des cours particuliers de mathématiques
  14. Préparer sa rentrée scolaire au mieux
  15. Comment prendre des cours particuliers de maths pendant le confinement COVID ?
  16. Choisir un prof particulier : focus sur la démarche à suivre
  17. L’évolution de l’école obligatoire
  18. Cours particuliers en ligne : une solution qui plaît
  19. Aides aux devoirs : comment s'organiser et pour quel tarif ?
  20. Comment choisir une calculatrice scientifique ?
  21. Faire appel à des étudiants pour des cours particuliers
  22. Quels sont les avantages du tutorat en ligne ?
  23. Améliorer ses compétences en mathématiques grâce aux cours particuliers en ligne
  24. Comment choisir le meilleur statut pour donner des cours particuliers ?
  25. Assurance scolaire pour étudiants : pourquoi et comment choisir les garanties adaptées ?
  26. Formation CAP Petite Enfance : détails, durée et perspectives professionnelles
  27. Pendant les vacances, stages, révisions ou soutien scolaire ?
  28. Protégez votre enfant : détecter le harcèlement scolaire
  29. Découvrez comment les diagrammes peuvent révolutionner votre compréhension des mathématiques
  30. Découvrir les Sciences : une exploration infatigable des mystères du monde
  31. Dessins numériques et avatars uniques : guide complet avec CapCut Online
  32. Le matériel pour une salle de classe confortable et propice à l'apprentissage
  33. Pourquoi choisir une prépa scientifique ?
  34. Le marché du soutien scolaire en France : tendances et solutions