Arithmétique/PGCD

Diviseurs communs à deux entiers naturels

Deux entiers naturels non tous deux nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont –1 et 1). Il existe donc un diviseur commun à ces deux nombres plus grand que les autres.

Conséquence : $b\mid a\iff \mathrm{pgcd}(a,b)=b$.

Algorithme d'Euclide

Modèle:Wikipédia Soient $a$ et $b$ deux entiers naturels tels que $b\ne 0$.

Opération	Reste $r$	Commentaire
on divise $a$ par $b$	$r_0$	$0\le r_0<b\text{ et }\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r_0)$
si $r_0\ne 0$, on divise $b$ par $r_0$	$r_1$	$0\le r_1<r_0\text{ et }\mathrm{pgcd}(b,r_0)=\mathrm{pgcd}(r_0,r_1)$
…	…	…
si $r_n\ne 0$, on divise $r_{n-1}$ par $r_n$	$0$	$\mathrm{pgcd}(r_{n-1},r_n)=r_n$

Modèle:Corollaire Ceci fournit une définition alternative du PGCD.

Propriétés du PGCD

Modèle:Exemple

Conséquence : si $k$ est un entier naturel non nul, diviseur commun à $a$ et $b$, alors $\mathrm{pgcd}(\frac{a}{k},\frac{b}{k})=\frac{1}{k}\times \mathrm{pgcd}(a,b)$.