PGCD de deux entiers

I. Définition du plus grand commun diviseur

Exemple :

Considérons la fraction $\dfrac{150}{42}$. La simplification de cette fraction peut être effectuée pas à pas, mais si on veut obtenir en une seule fois une fraction irréductible, alors il faut diviser le numérateur et le dénominateur par leur plus grand diviseur commun.

Soient Div(a) et Div(b) les ensembles des diviseurs de a et b.

Div(150) = {1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150}
et Div(42) = {1, 2, 3, 6, 7, 14, 21, 42}.

Alors PGCD(150, 42) = 6. et $\dfrac{150}{42}=\dfrac{6\times 25}{6\times 7}=\dfrac{25}{7}$.

Définition :

Soient Div$(a)$ et Div$(b)$ les ensembles des diviseurs respectifs des deux entiers naturels non nuls $a$ et $b$.

Le plus grand élément de l'intersection de Div$(a)$ et de Div$(b)$ est appelé plus grand commun diviseur de $a$ et de $b$. On le note $PGCD(a ; b)$ ou $a \wedge b$.

II. Propriétés du pgcd de deux entiers

$\circ$ $\text{Div} (a) \cap \text{Div} (b) = \text{Div} (a \wedge b).$

Cette propriété se formule également ainsi :

Théorème

Soient $a$, $b$ et $c$ trois entiers naturels non nuls.
$c | a$ et $c | b$ si et seulement si $c | a \wedge b$.

En raisonnant sur les ensembles de diviseurs, on obtient les résultats suivants :

Propriétés

Soient $a$, $b$ et $c$ trois entiers naturels non nuls.

$\circ$ $a \wedge b = b \wedge a$

$\circ$ $a \wedge (b \wedge c) = (a \wedge b) \wedge c$. Ce nombre est appelé PGCD de $a$, $b$ et $c$ et se note $a \wedge b \wedge c$.

$\circ$ $a \times (b \wedge c) = (ab) \wedge (ac)$

III. Recherche du pgcd en décomposant chaque nombre en facteurs premiers

Décomposons 150 et 144 en facteurs premiers.

$150 = 2^1 \times 3^1 \times 5^2$ et $144 = 2^4 \times 3^2$.

Tout diviseur commun à 150 et à 144 peut avoir :

$\circ$ le facteur premier 2, mais le plus grand exposant possible est 1 ;

$\circ$ le facteur premier 3, mais le plus grand exposant possible est 1.

Donc le plus grand diviseur commun à 150 et à 144 est $2^1 \times 3^1 = 6$.

Plus généralement, pour obtenir le PGCD de deux entiers naturels on peut procéder ainsi :

$\circ$ on décompose ces nombres en facteurs premiers ;

$\circ$ on fait le produit de tous les facteurs premiers communs en prenant pour chacun d’eux le plus petit exposant figurant dans les deux décompositions.

IV. Un point méthode : un exercice rédigé

Énoncé :

Soit $n \in \textbf{N}$. On pose $d = \text{PGCD}(2n+8 ~;~3n+15)$

a) Montrer que $d$ divise 6.

b) Déterminer l'ensemble $S$ des entiers relatifs tels que $d = 6$.

Solution :

a) On constate que $2n + 8 = 0$ pour $n = -4$ et que 3(-4) + 15 = 3 $\neq$ 0. On en conclut que $2n + 8$ et $3n + 15$ ne sont pas nuls simultanément. Par conséquent le PGCD a un sens.

$d = \text{PGCD}(2n+8~;~3n+15)$ divise $2n + 8$ et $3n + 15$.

Donc $d$ divise $2 \times (3n + 15) - 3(2n + 8) = 6n + 30 - 6n - 24 = 6$

b) On dresse le tableau des différentes valeurs prises par $2n + 8$ et $3n + 15$ modulo 6.

$d = 6$ si $2n + 8 \equiv 0$ (modulo 6) et $3n + 15 \equiv 0$ (modulo 6).

Ainsi $d = 6$ si $n \equiv 5$ (modulo 6) soit $S=\{6k+5\,;\,k\in\mathbb Z\}$