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

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

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}$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Exemple 1 — $3x + 5y = 1$

Étape 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.

$d = \mathrm{pgcd}(3,5) = 1$ et $1 \mid 1$ , donc des solutions existent.

Étape 2 —

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

L'équation est déjà réduite : $\mathrm{pgcd}(3,5)=1$ .

Étape 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)

Par inspection : $3 \times 2 + 5 \times (-1) = 6-5=1$ , donc $(x_0,y_0) = (2,-1)$ .

Étape 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}

Solutions : $x = 2+5k$ , $y = -1-3k$ , $k \in \mathbb{Z}$ .

Application guidée

Exemple 2 — $6x + 10y = 4$

Application autonome 1

Exemple 3 — $12x + 8y = 4$

Application autonome 2

Exemple 4 — $15x + 25y = 10$

Application autonome 3

Exemple 5 — $35x + 14y = 7$

Crée ton compte gratuit pour accéder à la fiche et aux exercices