En appliquant l’algorithme d’Euclide on obtient les divisions euclidiennes
successives :
495 = 147 × 3 + 54
147 = 54 × 2 + 39
54 = 39 × 1 + 15
39 = 15 × 2 + 9
15 = 9 × 1 + 6
9 = 6 × 1 + 3
6 = 3 × 2 + 0
Le pgcd est le dernier reste non nul, i.e. d = 3.
Afin de déterminer les coefficients de Bézout on reprend les égalités précédentes
dans l’ordre. Dans chacun, on exprime le reste en fonction du dividende et du diviseur et on reporte dans les suivantes : c’est l’algorithme d’Euclide étendu.
En utilisant les résultats précédents :
54 = 495 − 147 × 3
39 = 147 − 54 × 2
= 147 − (495 − 147 × 3) × 2
= 147 × 7 − 495 × 2
15 = 54 − 39
= (495 − 147 × 3) − (147 × 7 − 495 × 2)
= 495 × 3 − 147 × 10
9 = 39 − 15 × 2
= (147 × 7 − 495 × 2) − (495 × 3 − 147 × 10) × 2
= 147 × 27 − 495 × 8
6 = 15 − 9
= (495 × 3 − 147 × 10) − (147 × 27 − 495 × 8)
= 495 × 11 − 147 × 37
3 = 9 − 6
= (147 × 27 − 495 × 8) − (495 × 11 − 147 × 37)
= 147 × 64 − 495 × 19
On peut donc prendre (u,v) = (64,−19).
© Dunod. La photocopie non autorisée est un délit.
257
Chapitre 11 • Arithmétique
9782100547678-Fresl-C11.qxd 5/07/10 8:49 Page 257