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.

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)

.

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}

.

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