Démonstration de l'algorithme d'Euclide.

[invitedcd45209]

Bonjour,

Je viens de trouver ce site:
http://www.uel.education.fr/consulta...itre1-6det.htm
Il y a écrit que rk-1 divise rk-2, mais je ne comprends pas pourquoi c'est le PGCD de a et b.
Qk divise aussi rk-2 donc pourquoi ce n'est pas le PGCD?
-----

[invitef45cc474]

Salut
On a pgcd(r_i+2,_ri+1)=pgcd(r_i+1,r _i) pour tout i.
Donc comme ils disent, "de proche en proche" on obtient pgcd(a,b)=pgcd(b,r1)=...=pgcd( r_k-2,r_k-1)=r_k-2

De façon générale, si tu fais la division euclidienne de a par b: a=bq+r avec 0<=r<b alors tu as pgcd(a,b)=pgcd(b,r).
Ca vient du fait que d divise a et b si et seulement d divise b et r (ça se voit facilement).