PGCD et nombres premiers

Soit $a$ et $b$ deux entiers naturels non nuls :

• $PGCD(a ; 0) = a$
• $PGCD(a ; 1) = 1$
• Si $b$ divise $a$ alors $PGCD(a ; b) = b$

Démonstration de c) : Si $b$ divise $a$ alors tout diviseur de $b$ est un diviseur de $a$. Donc le plus grand diviseur de $b$ (qui est $b$) est un diviseur de $a$.

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)$.