Algorithme d'Euclide

[DjDjalilo]

Bonjour
Voilà j'aimerai savoir si a chaque fois quand on utilise l'algorithme d'Euclide pour calculer le pgcd on tombe toujours sur un reste nul ? si oui pourquoi ?
Merci pour votre aide !

[pascal16]

En gros, on crée une suite de restes strictement décroissante si reste >0, elle ne peut tomber que sur 0 à un moment (auquel cas la suite s’arrête).

[aviateur]

Bjr
Le principe de l'algo d' Euclide consiste à faire des divisions euclidiennes successives de la forme a=bq+ r
(dc r<b-1) et ainsi de réitérer avec le couple (b,r) ....
La suite des reste est strictement décroissante, on va bien finir par un reste nul.

[FLBP]

Salut,
si on veut calculer le pgcd(A,B) on remarque que dans le meilleur des cas B divise A, est donc en un temps constant on trouve B, avec un reste nul. Sinon dans le pire des cas on trouve un reste de B-1, ensuite un reste de B-2 est ainsi de suite jusqu'à B-B=0, ce qui démontre d'une complexité linéaire à B.