Equations diophantiennes : Méthode et exercice corrigé

Comment résoudre les équations diophantiennes de terminale ou du début du supérieure ? Réponse dans cet article !
Equations diophantiennes

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}
(-8,3) est donc une solution particulière. On va donc maintenant remarquer que 1 = 27 \times 3 - 10 \times 8 = 10 x + 27 y . Ainsi, 10 (x+8) = 27 (3 - y)

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

Total
0
Partages

Laisser un commentaire

Articles similaires