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 = c$ en nombres entiers.

Résumé

Pour trouver les solutions $x$, $y$ en nombres entiers à l’équation $ax + by = c$ avec $a$, $b$ 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

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

Condition nécessaire

Supposons que $x$, $y$ soit une solution en nombres entiers de cette équation.

Alors on peut exprimer $y$ en fonction de $x$ pour obtenir :

$y = \dfrac{10 - 39x}{14}$

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

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

Du fait que $x$ et $y$ sont des nombres entiers, la quantité

$p = \dfrac{10 - 11x}{14}$

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

et d’autre part, $x$ et $p$ sont tels que :

$\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 $x$ en fonction de $p$ ; on obtient :

$\begin{aligned} x = \dfrac{10 -14p}{11}= \dfrac{10 - 3p}{11}- p&& (5)\\ \end{aligned}$

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

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

où $q$ et $p$ sont solutions de l’équation diophantienne

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

Exprimant $p$ en fonction de $q$, on obtient :

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

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

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

où $q$ et $r$ sont solutions de l’équation diophantienne :

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

On exprime alors $q$ en fonction de $r$ ; ainsi :

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

et en posant

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

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

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

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

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

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

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

On peut donc remplacer $r$ et $q$ dans $(9)$ par leurs expressions en fonction de $s$ pour obtenir l’expression de $p$ en fonction de $s$

$\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

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

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

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

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

Condition suffisante

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

Or, on a : $39 \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
$\begin{aligned} x = 14s - 8 \\ et \\ y = -39s + 23 && (19)\\ \end{aligned}$
pour tout $s$ entier relatif.

2 - Application pratique de la méthode

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

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

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

On commence avec :

$y = \dfrac{81 - 8x}{5}= \dfrac{1 -3x}{5}+ 16 - x$.

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

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

On exprime : $x = \dfrac{1 - 5p}{3}=\dfrac{1 -2p}{3}-p$.

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

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

On exprime

$p=\dfrac{1-3q}{2} = \dfrac{1-q}{2}-q$

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

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

Ainsi on a : $q = 1 -2r$.

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

Ensuite :

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

Enfin

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

On vérifie que :

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

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

$\boxed{x = 2 -5r, y= 13 + 8r}$ ($r$ 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 :

Par Zauctore