Dans cet article, nous allons nous intéresser aux équations diophantiennes, mais à un type bien particulier, celui qu’on voit en terminale ou au début dans le supérieur.
Prérequis
Définition
Une équation diophantienne est une équation polynomiale à une ou plusieurs inconnues dont la solution recherchée est un entier. Dans cet article, nous allons nous intéresser à un cas particulier : les équations de la forme au + bv =c avec a,b et c trois entiers relatifs et (u,v) \in \Z inconnues de l’équation
Méthode
Cas c = 1
Commençons d’abord par le. cas c = 1, c’est à dire qu’on va chercher à trouver les entiers relatifs u et v tels que au+bv = 1 . Voici la méthode de résolution de cette équation :
- Vérifier que \text{PGCD}(a,b) = 1. Si ce n’est pas le cas alors on n’aura pas de solution (théorème de Bézout)
- Trouver une solution particulière à l’équation (u_0,v_0). 2 solutions pour ces deux premiers points :
- On peut intuiter la solution particulière
- Mais la méthode systématique qui fonctionne tout le temps est de remonter l’algorithme d’Euclide (cf exercice corrigé ci-dessous – voir aussi nos exercices sur le théorème de Bézout)
- On sait que au+bv = 1 et que au_0 + bv_0 = 1 . On peut donc écrire au+bv = au_0 + bv_0 \iff a(u-u_0) = b(v_0-v)
- On en déduit ensuite que b | a (u-u_0) . Comme \text{PGCD}(a,b) = 1, le théorème de Gauss nous indique que b | u -u_0 . On peut donc écrire u - u_0 = kb .
- Si on remplace dans l’équation ci-dessus, on obtient akb = b(v_0-v) \iff v_0 - v = ka .
- On a donc un ensemble de candidats : (u,v) = \{ (u_0+kb,v_0-ka), k \in \Z\}
- Il faut vérifier que ces solutions fonctionnent. On a a (u_0+kb)+ b(v_0-ka)= akb + u_0 a -akb +v_0b = u_0a + v_0b = 1
Cas quelconque
On ne vas pas tout réécrire car ne serait que répétition. Voici ce qui change :
- La première étape devient : on calcule d = \text{PGCD}(a,b) . Si d | c alors on divise tout par c. Sinon, on n’a pas de solution.
- On va alors ensuite résoudre a'u +b' v = 1 avec a' = \dfrac{a}{d}, b' = \dfrac{b}{d} .
- Une fois qu’on trouvé les solutions, on les multiplie par c' = \dfrac{c}{d} pour retourner à l’équation de base.
Exercice corrigé
Enoncé : Trouver toutes les solutions entières de 10x + 27y = 1
Corrigé : On utilise l’algorithme d’Euclide pour trouver le PGCD et pour
\begin{array}{ll}
27 &= 10 \times 2 + 7\\
10 & = 7 \times 1 + 3\\
7 &= 3 \times 2 +1
\end{array}Ce qui montre bien que le PGCD vaut 1. On remonte maintenant l’algorithme d’Euclide pour trouver un couple solution :
\begin{array}{ll}
1 &= 7 - 3 \times 2 \\
& = 7 - (10- 7 \times 1 ) \times 2 \\
& = 7\times 3 - 10 \times 2 \\
&= (27 - 10 \times 2 ) \times 3 - 10 \times 2 \\
& = 27 \times 3 - 10 \times 8
\end{array}On en déduit que 27 | 10(x+8) . Or, \text{PGCD}(27,10) = 1 . Donc, d’après le théorème de Gauss, on a 27 | x+8 \iff \exists k \in \Z x+8 = 27k
Si on réinjecte dans l’équation, on obtient : 10 \times 27k = 27 (3-y) \iff 3-y = 10k . On obtient alors comme candidats (x,y) = (27k-8, 3-10k ) . Ces solutions sont bonnes, en effet : 10 \times( 27k-8) + 27 \times (3-10k ) = 81-80 +270k-270k = 1
