Étape 1
On applique l'algorithme d'Euclide aux entiers 37 et 24 :
Étape 2
$$37 = 1 \times 24 + 13$$
Étape 3
$$24 = 1 \times 13 + 11$$
Étape 4
$$13 = 1 \times 11 + 2$$
Étape 5
$$11 = 5 \times 2 + 1$$
Étape 6
Le dernier reste non nul est 1, donc $\text{PGCD}(37, 24) = 1$. D'après le théorème de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $37u + 24v = 1$.
Étape 7
On remonte les divisions successives pour exprimer 1 en fonction de 37 et 24 :
Étape 8
$$1 = 11 - 5 \times 2$$
Étape 9
En remplaçant $2$ par $13 - 1 \times 11$ :
Étape 10
$$1 = 11 - 5 \times (13 - 11) = 6 \times 11 - 5 \times 13$$
Étape 11
En remplaçant $11$ par $24 - 1 \times 13$ :
Étape 12
$$1 = 6 \times (24 - 13) - 5 \times 13 = 6 \times 24 - 11 \times 13$$
Étape 13
En remplaçant $13$ par $37 - 1 \times 24$ :
Étape 14
$$1 = 6 \times 24 - 11 \times (37 - 24) = -11 \times 37 + 17 \times 24$$
Étape 15
On obtient une solution particulière avec $u_0 = -11$ et $v_0 = 17$.
Étape 16
Les solutions entières de l'équation sont de la forme $u = -11 + 24k$ où $k \in \mathbb{Z}$.
Étape 17
Pour satisfaire la condition $0 \le u < 24$, on choisit $k = 1$, ce qui donne $u = -11 + 24 = 13$.
Méthode clé
Remonter les égalités de l'algorithme d'Euclide pour exprimer 1 sous la forme $37u_0 + 24v_0 = 1$, puis ajouter un multiple adéquat de 24 pour respecter la condition d'encadrement.
Piège à éviter
Attention aux signes lors du développement des parenthèses pendant la phase de remontée des restes.
