Vérification propriété de l'algorithme d'Euclide

[Math34]

Bonsoir à tous !
J'ai un doute concernant une propriété éventuelle des restes des divisions successives de l'algorithme d'Euclide.
Est-il bien vrai que ce reste est toujours un multiple du PGCD ?

Merci d'avance.

[LN1]

Vrai

cela tient de la propriété
pgcd(a ; b) = pgcd(b ; a - bq) pour tout entier q (a fortiori pour q = quotient)

Qui tient de la propriété
l'ensemble des diviseurs communs à a et b = ensemble des diviseurs communs à b et a - bq

dem :
1) si d est un diviseur de a et de b alors d est aussi diviseur de a - bq donc est diviseur de b et a - bq

2) si d est diviseur de b et a - bq alors d est aussi diviseur de (a - bq) + bq donc d est diviseur de b et a