Comment résoudre une équation diophantienne $ax + by = c$ ?

En vérifiant $d = \mathrm{pgcd}(a,b) \mid c$ , en trouvant une solution particulière $(x_0, y_0)$ par l'algorithme de Bézout, puis en décrivant l'ensemble des solutions

L'objectif

Trouver toutes les solutions entières $(x,y)$ de $ax+by=c$ .

Le principe

L'équation $ax+by=c$ admet des solutions entières si et seulement si $\mathrm{pgcd}(a,b) \mid c$ (théorème de Bézout).

La méthode

1
Calculer $d = \mathrm{pgcd}(a,b)$ par l'algorithme d'Euclide. Si $d \nmid c$ , conclure qu'il n'y a pas de solution.
Comment calculer le PGCD de deux entiers ?Voir
2
Si $d \mid c$ , diviser par $d$ : résoudre $\frac{a}{d}x + \frac{b}{d}y = \frac{c}{d}$ (avec $\mathrm{pgcd}(\frac{a}{d},\frac{b}{d})=1$ ).
3
Trouver une relation de Bézout $\frac{a}{d} u + \frac{b}{d} v = 1$ (par remontée de l'algorithme d'Euclide), puis multiplier par $\frac{c}{d}$ pour obtenir $(x_0, y_0)$ .
Comment exprimer le PGCD sous la forme de Bézout $au + bv$ ?Voir
4
L'ensemble des solutions est $\left\{ $$\begin{array}{l} x = x_0 + \frac{b}{d}k \\ y = y_0 - \frac{a}{d}k \end{array}$$ \right.$ , $k \in \mathbb{Z}$ .

Difficulté croissante de 1 à 5

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En vérifiant d=pgcd(a,b)∣cd = \mathrm{pgcd}(a,b) \mid cd=pgcd(a,b)∣c, en trouvant une solution particulière (x0,y0)(x_0, y_0)(x0​,y0​) par l'algorithme de Bézout, puis en décrivant l'ensemble des solutions