Introduction : Les Outils de l’Arithmétique
Les notions de Plus Grand Commun Diviseur (PGCD) et de Plus Petit Commun Multiple (PPCM) sont des concepts centraux de l’arithmétique. Elles permettent de quantifier les relations de divisibilité entre les éléments d’un anneau. Dans les anneaux euclidiens comme l’anneau des entiers $\mathbb{Z}$ et l’anneau des polynômes $K[X]$, ces notions sont particulièrement bien définies et calculables grâce à l’algorithme d’Euclide.
Le PGCD et le PPCM ne sont pas seulement des outils de calcul ; ils sont profondément liés à la structure des idéaux de l’anneau. Comprendre leur définition et leurs propriétés est donc essentiel pour maîtriser l’arithmétique dans ces structures fondamentales.
Le Plus Grand Commun Diviseur (PGCD)
Le PGCD de deux éléments est, comme son nom l’indique, le plus grand des diviseurs qu’ils ont en commun. La notion de « plus grand » est à comprendre au sens de la divisibilité.
Soit $A$ un anneau principal (comme $\mathbb{Z}$ ou $K[X]$). Soient $a, b \in A$, non tous les deux nuls. Un élément $d \in A$ est un PGCD de $a$ et $b$ si :
- $d$ est un diviseur commun : $d|a$ et $d|b$.
- $d$ est le « plus grand » des diviseurs communs : pour tout autre diviseur commun $c$ (si $c|a$ et $c|b$), on a $c|d$.
Unicité : Le PGCD n’est unique qu’à un facteur inversible près.
- Dans $\mathbb{Z}$, si $d$ est un PGCD, $-d$ l’est aussi. On choisit par convention le PGCD positif.
- Dans $K[X]$, si $D(X)$ est un PGCD, tout polynôme $cD(X)$ où $c \in K^*$ l’est aussi. On choisit par convention le PGCD unitaire (dont le coefficient dominant est 1).
Calcul du PGCD : l’Algorithme d’Euclide
Dans un anneau euclidien, le PGCD est calculé efficacement par l’algorithme d’Euclide, qui repose sur des divisions euclidiennes successives. Le PGCD est le dernier reste non nul de l’algorithme.
Exemple dans $\mathbb{Z}$
Calculons le PGCD de 1071 et 462.
$1071 = 2 \cdot 462 + 147$
$462 = 3 \cdot 147 + 21$
$147 = 7 \cdot 21 + 0$
Le dernier reste non nul est 21. Donc $\text{pgcd}(1071, 462) = 21$.
Exemple dans $\mathbb{R}[X]$
Calculons le PGCD de $A(X) = X^4 – 1$ et $B(X) = X^3 – 2X^2 + X – 2$.
$X^4 – 1 = (X+2)(X^3 – 2X^2 + X – 2) + (3X^2 + 3)$
$X^3 – 2X^2 + X – 2 = (\frac{1}{3}X – \frac{2}{3})(3X^2+3) + 0$
Le dernier reste non nul est $3X^2+3$. Le PGCD unitaire est donc $\frac{1}{3}(3X^2+3) = X^2+1$.
Le Plus Petit Commun Multiple (PPCM)
Le PPCM est le dual du PGCD : c’est le plus petit des multiples communs.
Soit $A$ un anneau principal. Soient $a, b \in A$ non nuls. Un élément $m \in A$ est un PPCM de $a$ et $b$ si :
- $m$ est un multiple commun : $a|m$ et $b|m$.
- $m$ est le « plus petit » des multiples communs : pour tout autre multiple commun $c’$ (si $a|c’$ et $b|c’$), on a $m|c’$.
Le PPCM est, comme le PGCD, unique à un facteur inversible près.
Calcul du PPCM
Le calcul du PPCM est généralement effectué via une relation fondamentale qui le lie au PGCD.
Dans un anneau principal, pour tous éléments $a, b$ non nuls, on a la relation : $$ \text{pgcd}(a, b) \cdot \text{ppcm}(a, b) \text{ est associé à } ab $$ Cela se traduit par les formules :
- Dans $\mathbb{Z}$ : $\text{ppcm}(a,b) = \frac{|ab|}{\text{pgcd}(a,b)}$
- Dans $K[X]$ : $\text{ppcm}(A,B) = \frac{A \cdot B}{\text{pgcd}(A,B)}$ (à un facteur constant près)
Exemple dans $\mathbb{Z}$
Pour 1071 et 462, on a trouvé $\text{pgcd}(1071, 462) = 21$.
$\text{ppcm}(1071, 462) = \frac{1071 \times 462}{21} = 1071 \times 22 = 23562$.
Lien avec la Théorie des Idéaux
Les notions de PGCD et PPCM ont une interprétation très naturelle en termes d’idéaux, qui éclaire leur signification profonde.
Soit $A$ un anneau principal et $a, b \in A$.
- L’idéal engendré par le PGCD de $a$ et $b$ est égal à l’idéal somme de $(a)$ et $(b)$ : $$ ( \text{pgcd}(a, b) ) = (a) + (b) = \{au + bv \mid u,v \in A\} $$ C’est une autre façon d’énoncer le théorème de Bézout.
- L’idéal engendré par le PPCM de $a$ et $b$ est égal à l’idéal intersection de $(a)$ et $(b)$ : $$ ( \text{ppcm}(a, b) ) = (a) \cap (b) $$