-
À l'aide de l'algorithme d'Euclide, calculer $\mathrm{PGCD}(1386, 588)$.
-
En remontant l'algorithme, déterminer deux entiers relatifs $u$ et $v$ tels que $1386u + 588v = \mathrm{PGCD}(1386, 588)$.
-
En déduire que $\dfrac{1386}{42}$ et $\dfrac{588}{42}$ sont des entiers premiers entre eux.
Commencer par la division de $1386$ par $588$, puis diviser le diviseur par le reste, et ainsi de suite.
Écrire chaque reste sous la forme « dividende − quotient × diviseur » et partir de la ligne qui donne le PGCD.
Diviser la relation de Bézout obtenue par $42$ et appliquer le théorème de Bézout.
1. Algorithme d'Euclide : $$\begin{aligned} 1386 &= 2 \times 588 + 210 \\ 588 &= 2 \times 210 + 168 \\ 210 &= 1 \times 168 + 42 \\ 168 &= 4 \times 42 + 0 \end{aligned}$$ Le dernier reste non nul est $42$, donc $\mathrm{PGCD}(1386, 588) = 42$.
2. On écrit les restes : $42 = 210 - 168$, $168 = 588 - 2 \times 210$, $210 = 1386 - 2 \times 588$. On remonte : $$\begin{aligned} 42 &= 210 - 168 = 210 - (588 - 2 \times 210) = 3 \times 210 - 588 \\ &= 3(1386 - 2 \times 588) - 588 = 3 \times 1386 - 7 \times 588. \end{aligned}$$ Vérification : $3 \times 1386 = 4158$, $7 \times 588 = 4116$ et $4158 - 4116 = 42$. On peut prendre $u = 3$ et $v = -7$.
3. On a $1386 = 42 \times 33$ et $588 = 42 \times 14$. En divisant la relation $3 \times 1386 - 7 \times 588 = 42$ par $42 \neq 0$ : $$3 \times 33 - 7 \times 14 = 1.$$ Vérification : $99 - 98 = 1$. D'après le théorème de Bézout, $33$ et $14$ sont premiers entre eux.
PGCD = 42 ; 3 × 1386 − 7 × 588 = 42 ; 33 et 14 premiers entre eux