Soit a et b deux entiers naturels non nuls, et r le reste de la division euclidienne de a par b. On a :PGCD(a;b)=PGCD(b;r)Démonstration : Si D est un diviseur de b et r, alors D divise a=bq+r, donc D est un diviseur de a et b. Réciproquement, si D divise a et b, alors D divise r=a−bq, donc D est un diviseur de b et r. L'ensemble des diviseurs communs de a et b est égal à celui de b et r, d'où PGCD(a;b)=PGCD(b;r).
