Arithmétique/PGCD

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

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.

Définition

Le PGCD de deux entiers naturels a et b non tous deux nuls, noté pgcd(a, b), est leur plus grand diviseur commun.

Conséquence : $b\mid a\Leftrightarrow \operatorname {pgcd} \left(a,b\right)=b$.

Lemme pour l'algorithme d'Euclide

Début d'un lemme

Lemme

Soient $b,r\in \mathbb {N} ^{*}$ et $q\in \mathbb {N}$, alors : $\operatorname {pgcd} \left(bq+r,b\right)=\operatorname {pgcd} \left(b,r\right)$.

Fin du lemme

Démonstration

Il suffit de démontrer que $bq+r$ et $b$ ont mêmes diviseurs communs que $b$ et $r$.

Soit $d$ un diviseur de $bq+r$ et $b$, alors $d$ divise $(bq+r)-bq=r$.

Réciproquement, soit $d$ un diviseur de $b$ et $r$, alors $d$ divise $bq+r$.

 

Algorithme d'Euclide

Soient $a$ et $b$ deux entiers naturels tels que $b\neq 0$.

Opération	Reste $r$	Commentaire
on divise $a$ par $b$	$r_{0}$	$0\leq r_{0}<b{\text{ et }}\operatorname {pgcd} (a,b)=\operatorname {pgcd} (b,r_{0})$
si $r_{0}\neq 0$, on divise $b$ par $r_{0}$	$r_{1}$	$0\leq r_{1}<r_{0}{\text{ et }}\operatorname {pgcd} (b,r_{0})=\operatorname {pgcd} (r_{0},r_{1})$
…	…	…
si $r_{n}\neq 0$, on divise $r_{n-1}$ par $r_{n}$	$0$	$\operatorname {pgcd} (r_{n-1},r_{n})=r_{n}$

Propriété

Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.

Corollaire

Les diviseurs communs à deux entiers naturels a et b non tous deux nuls sont les diviseurs de pgcd(a, b).

Ceci fournit une définition alternative du PGCD.

Propriétés du PGCD

Propriété

Si l’on multiplie deux entiers naturels non tous deux nuls a et b par un même entier naturel non nul k, leur PGCD est multiplié par k, c'est-à-dire :

$\operatorname {pgcd} (ka,kb)=k\times \operatorname {pgcd} (a,b)$.

Démonstration

L'entier k divise ka et kb donc aussi leur PGCD. L'entier d > 0 défini par pgcd(ka, kb) = kd vérifie alors :

$\forall n\in \mathbb {Z} \quad n\mid a,b\iff kn\mid ka,kb\iff kn\mid pgcd(ka,kb)\iff n\mid d$

donc

$\operatorname {pgcd} (a,b)=d=\operatorname {pgcd} (ka,kb)/k$

.

 

Début de l'exemple

Exemple : calcul de $\operatorname {pgcd} (12000,32000)$

$12000=12\times 1000$ et $32000=32\times 1000$

donc $\operatorname {pgcd} (12000,32000)=1000\times \operatorname {pgcd} (12,32)=4000$.

Fin de l'exemple

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

Extension du PGCD aux entiers relatifs

Définition

Le PGCD de deux entiers relatifs non nuls $a$ et $b$ est le PGCD de leurs valeurs absolues, c'est-à-dire $\operatorname {pgcd} (a,b)=\operatorname {pgcd} (|a|,|b|)$.

Remarque

• $\forall k\in \mathbb {Z} ^{*}\quad \operatorname {pgcd} (ka,kb)=|k|\operatorname {pgcd} (a,b)$
• Les diviseurs communs à $a$ et $b$ sont encore les diviseurs de $\operatorname {pgcd} (a,b)$

Nombres premiers entre eux

Définition

Deux entiers relatifs $a$ et $b$ non tous deux nuls sont dits premiers entre eux si $\operatorname {pgcd} (a,b)=1$.

Début de l'exemple

Exemple

$35$ et $26$ sont premiers entre eux, car leur seul diviseur commun positif est $1$.

Fin de l'exemple

Propriété

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls, $d$ leur PGCD, et $a',b'$ les entiers définis par $a=da'$ et $b=db'$. Alors, $a'$ et $b'$ sont premiers entre eux.

Démonstration

$d$ est non nul et divise $a$ et $b$ donc :

• $a':={\frac {a}{d}}$ et $b':={\frac {b}{d}}$ sont bien définis et sont bien des entiers ;
• $\operatorname {pgcd} (a',b')={\frac {\operatorname {pgcd} (da',db')}{d}}={\frac {\operatorname {pgcd} (a,b)}{d}}=1$.