Résoudre une équation diophantienne ax+by=c
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
On cherche à déterminer tous les couples d'entiers relatifs $ \left(x ; y\right) $ solutions de l'équation :
où $ a $, $ b $ et $ c $ sont des entiers relatifs donnés.
- Étape 1 : calculer $ d=\text{PGCD}\left(a ; b\right) $. L'équation admet des solutions si et seulement si $ d $ divise $ c $.
- Étape 2 : diviser l'équation par $ d $ pour se ramener à $ a^{\prime}x+b^{\prime}y=c^{\prime} $ avec $ a^{\prime} $ et $ b^{\prime} $ premiers entre eux.
- Étape 3 : trouver une solution particulière $ \left(x_{0} ; y_{0}\right) $ (à l'aide de l'algorithme d'Euclide étendu, ou par essais).
- Étape 4 : soustraire les deux égalités et appliquer le théorème de Gauss pour obtenir la solution générale.
Remarque
Si $ \left(x_{0} ; y_{0}\right) $ est une solution particulière de $ a^{\prime}x+b^{\prime}y=c^{\prime} $ avec $ \text{PGCD}\left(a^{\prime} ; b^{\prime}\right)=1 $, alors l'ensemble des solutions est :
Résoudre 5x+3y=11 dans Z×Z
Étape 1 : $ \text{PGCD}\left(5 ; 3\right)=1 $ (car $ 5 $ et $ 3 $ sont premiers entre eux). Comme $ 1 $ divise $ 11 $, l'équation admet des solutions.
Étape 2 : $ a $ et $ b $ sont déjà premiers entre eux, on garde l'équation telle quelle.
Étape 3 : on cherche une solution particulière.
On commence par résoudre $ 5u+3v=1 $. On remarque que $ 5\times \color{red}{2}\color{black}+3\times \color{red}{\left( - 3\right)}\color{black}=10 - 9=1 $.
Donc $ \left(u ; v\right)=\left(2 ; - 3\right) $ vérifie $ 5u+3v=1 $.
En multipliant par $ 11 $ : $ 5\times 22+3\times \left( - 33\right)=11 $.
Une solution particulière est donc $ \left(x_{0} ; y_{0}\right)=\left(22 ; - 33\right) $.
Étape 4 : soit $ \left(x ; y\right) $ une solution quelconque. On a :
- $ 5x+3y=11 $
- $ 5\times 22+3\times \left( - 33\right)=11 $
Par soustraction : $ 5\left(x - 22\right)+3\left(y+33\right)=0 $, soit :
$ 3 $ divise $ 5\left(x - 22\right) $. Or $ \text{PGCD}\left(5 ; 3\right)=1 $, donc d'après le théorème de Gauss, $ 3 $ divise $ x - 22 $.
Il existe donc un entier $ k $ tel que $ x - 22=3k $, c'est-à-dire $ x=22+3k $.
En reportant dans l'égalité : $ 5\times 3k= - 3\left(y+33\right) $ d'où $ y= - 33 - 5k $.
Réciproquement, on vérifie que pour tout $ k\in \mathbb{Z} $, le couple $ \left(22+3k ; - 33 - 5k\right) $ est solution :
Conclusion : l'ensemble des solutions est $ \left\{\left(22+3k ; - 33 - 5k\right) , k\in \mathbb{Z}\right\} $.
Résoudre 12x+8y=20 dans Z×Z
Étape 1 : $ \text{PGCD}\left(12 ; 8\right)=4 $. Comme $ 4 $ divise $ 20 $, l'équation admet des solutions.
Étape 2 : on divise par $ 4 $ : l'équation devient $ 3x+2y=5 $, avec $ \text{PGCD}\left(3 ; 2\right)=1 $.
Étape 3 : $ \left(x_{0} ; y_{0}\right)=\left(1 ; 1\right) $ est solution évidente : $ 3\times 1+2\times 1=5 $.
Étape 4 : soit $ \left(x ; y\right) $ une autre solution.
$ 3x+2y=5 $ et $ 3\times 1+2\times 1=5 $.
Par soustraction : $ 3\left(x - 1\right)= - 2\left(y - 1\right) $.
$ 2 $ divise $ 3\left(x - 1\right) $ et $ \text{PGCD}\left(3 ; 2\right)=1 $ donc d'après le théorème de Gauss, $ 2 $ divise $ x - 1 $.
Il existe $ k\in \mathbb{Z} $ tel que $ x - 1=2k $, soit $ x=1+2k $.
En reportant : $ 3\times 2k= - 2\left(y - 1\right) $ d'où $ y=1 - 3k $.
Vérification : $ 12\left(1+2k\right)+8\left(1 - 3k\right)=12+24k+8 - 24k=20 $. C'est bien le cas.
Conclusion : $ S=\left\{\left(1+2k ; 1 - 3k\right) , k\in \mathbb{Z}\right\} $.
Remarque
Pour des coefficients plus gros, l'algorithme d'Euclide étendu (voir la fiche méthode dédiée) fournit systématiquement une solution particulière.
Attention
Trois pièges à éviter :
- Ne pas oublier la condition d'existence : si $ \text{PGCD}\left(a ; b\right) $ ne divise pas $ c $, l'équation n'a aucune solution entière.
- Bien diviser par le PGCD avant d'utiliser le théorème de Gauss : celui-ci exige que les coefficients soient premiers entre eux.
- Ne pas oublier la réciproque : après avoir établi la forme des solutions, vérifier que tout couple de cette forme est bien solution. Sinon, on aurait montré seulement un sens (condition nécessaire).