PGCD-Nombres premiers entre eux

Définition : Si a et b sont deux entiers, on appelle PGCD (Plus Grand Commun Diviseur) de a et b le plus grand des diviseurs communs de a et de b.

Exemple : L'ensemble des diviseurs de 45 est D₄₅ = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }.
L'ensemble des diviseurs de 63 est D₆₃ = { 1 ; 3 ; 7 ; 9 ; 21 ; 63 }.
L'ensemble de leurs diviseurs communs est D₄₅D₆₃ = { 1 ; 3 ; 9 }.
Leur plus grand diviseur commun est 9. PGCD( 45 ; 63 ) = 9.

Exemple : Calcul du PGCD de 4851 et de 616.

donc le PGCD de 4851 et de 616 est 77, le dernier reste non nul.

Le programme de calcul du PGCD
Données :  deux entiers naturels a et b, a > b.
Résultat : PGCD( a ; b ).
Règle :
Tant que b > 0, faire :
         

Retourner à b ← r signifie que dans le registre noté b, on met le contenu du registre noté r.

Théorèmes
Si c est un diviseur de a et un diviseur de b, alors c est un diviseur du PGCD de a et de b.

Exemple : Tout diviseur de 4851 et de 616 est diviseur de leur PGCD, 77.

Exemple: PGCD( 187 ; 17 ) = 17.