Plus petit commun multiple

En mathématiques, et plus précisément en arithmétique, le plus petit commun multiple – en abrégé PPCM – (peut s'appeler aussi PPMC, soit « plus petit multiple commun ») de deux entiers non nuls a et b est le plus petit entier strictement positif qui soit multiple de ces deux nombres. On le note a ∨ b^[1] ou PPCM(a, b), ou parfois simplement [a, b]^[2].

Diagramme de Venn montrant les plus petits communs multiples de 2, 3, 4, 5 et 7.

Plus généralement, le PPCM se définit pour un nombre quelconque d'éléments : le PPCM de n entiers non nuls est le plus petit entier strictement positif multiple simultanément de ces n entiers.

On peut également définir le PPCM de a et b comme un multiple commun de a et de b qui divise tous les autres. Cette seconde définition se généralise à un anneau commutatif quelconque, mais on perd en général l'existence et l'unicité ; on parle alors d'un PPCM de deux éléments. L'existence est assurée dans les anneaux factoriels.

PPCM de nombres entiers

Définition et existence

La définition historique du PPCM a été établie par Euclide pour deux entiers naturels non nuls : PPCM (a, b) est le plus petit entier naturel non nul qui soit multiple de a et de b , où a et b sont des entiers naturels non nuls^[3].

Cette définition a été élargie depuis au cas où l'un des entiers est nul par la définition : PPCM (a, 0) = 0. Puis au cas de tous les entiers, par la définition : PPCM(a, b) = PPCM (|a|, |b|) avec |a| = a si a > 0 et |a| = - a sinon.

La définition moderne du PPCM est donc la suivante, pour a et b entiers relatifs :

• si a ou b est nul, PPCM(a, b) = 0 ;
• si a et b sont non nuls, l'ensemble des entiers strictement positifs qui sont multiples à la fois de a et de b est non vide, car il contient |ab|. Il possède donc un plus petit élément^[4], et c'est cet entier (strictement positif) que l'on appelle le PPCM de a et b :

${\displaystyle \operatorname {PPCM} (a,b)=\min \left(\left\{m\in \mathbb {N} ^{*}\mid a|m~{\rm {et}}~b|m\right\}\right)}$.

Cette définition peut être étendue à un nombre quelconques d'entiers, avec, par exemple pour trois entiers a, b, c :

${\displaystyle \operatorname {PPCM} (a,b,c)=\min \left(\left\{m\in \mathbb {N} ^{*}\mid a|m~{\rm {,}}~b|m{\rm {,}}~c|m\right\}\right)}$.

Tous les raisonnements et toutes les propriétés du PPCM d'entiers relatifs sont donc ceux du PPCM d'entiers naturels : dans la suite de ce chapitre, les nombres a, b, c, etc. seront donc supposés être des entiers positifs ou nuls.

Propriétés

Soient a, b, c trois entiers naturels.

• ${\displaystyle \operatorname {PPCM} (a,a)=a}$^[5]
• ${\displaystyle \operatorname {PPCM} (a,b)=\operatorname {PPCM} (b,a)}$^[5]
• les multiples communs à a et b sont les multiples de ${\displaystyle \operatorname {PPCM} (a,b)}$^[6]; en particulier : ${\displaystyle \operatorname {PPCM} (a,b)=a\iff b\mid a}$
• ${\displaystyle \operatorname {PPCM} (ac,bc)=c\operatorname {PPCM} (a,b)}$^[6]
• ${\displaystyle (b-a)\operatorname {PPCM} (a,b)=b\operatorname {PPCM} (a,b-a)}$ pour ${\displaystyle b\geqslant a}$^[5]
• ${\displaystyle \operatorname {PPCM} (a,b,c)=\operatorname {PPCM} (\operatorname {PPCM} (a,b),c)=\operatorname {PPCM} (a,\operatorname {PPCM} (b,c))}$, propriété qui peut être étendue à un nombre arbitraire d'éléments et qui montre qu'on peut calculer le PPCM de plusieurs nombres progressivement à partir du PPCM de deux nombres

Relations entre PPCM et PGCD

Le PPCM et le plus grand commun diviseur (PGCD) de nombres entiers sont reliés par plusieurs formules, notamment :

• ${\displaystyle \operatorname {PPCM} (a,b)\times \operatorname {PGCD} (a,b)=ab}$^[7]
• ${\displaystyle \operatorname {PGCD} (a,\operatorname {PPCM} (a,b))=\operatorname {PPCM} (a,\operatorname {PGCD} (a,b))=a}$
• ${\displaystyle \operatorname {PGCD} (a,\operatorname {PPCM} (b,c))=\operatorname {PPCM} (\operatorname {PGCD} (a,b),\operatorname {PGCD} (a,c))}$
• ${\displaystyle \operatorname {PPCM} (a,\operatorname {PGCD} (b,c))=\operatorname {PGCD} (\operatorname {PPCM} (a,b),\operatorname {PPCM} (a,c))}$
• ${\displaystyle \operatorname {PGCD} (\operatorname {PPCM} (a,b),\operatorname {PPCM} (b,c),\operatorname {PPCM} (a,c))=\operatorname {PPCM} (\operatorname {PGCD} (a,b),\operatorname {PGCD} (b,c),\operatorname {PGCD} (a,c))}$.

PPCM et facteurs premiers

D'après le théorème fondamental de l'arithmétique, tout entier n naturel non nul s'écrit de manière unique à l'ordre près des facteurs comme un produit fini de nombres premiers. Donc si ${\displaystyle a}$ et ${\displaystyle b}$ sont deux entiers, et ${\displaystyle p_{1},p_{2}}$, …, ${\displaystyle p_{k}}$ sont les nombres premiers, rangés en ordre croissant, qui divisent ${\displaystyle a}$ ou ${\displaystyle b}$, la décomposition de ${\displaystyle a}$ en produit de facteurs premiers est de la forme ${\displaystyle a=p_{1}^{v_{p_{1}}(a)}\times p_{2}^{v_{p_{2}}(a)}\times }$…..${\displaystyle \times p_{k}^{v_{p_{k}}(a)}}$ = ${\displaystyle \prod _{i=1}^{k}{p_{i}}^{v_{p_{i}}(a)}}$^[8]. De même, celle de ${\displaystyle b}$ est de la forme ${\displaystyle b=\prod _{i=1}^{k}{p_{i}}^{v_{p_{i}}(b)}}$. Alors ^[9]: ${\displaystyle \mathrm {PPCM} (a,b)=\prod _{i=1}^{k}{p_{i}}^{\max(v_{p_{i}}(a),v_{p_{i}}(b))}}$.

Cette propriété permet de calculer le PPCM de toute famille d'entiers, et de démontrer que tout multiple commun aux éléments de cette famille est un multiple de leur PPCM.

Calcul du PPCM de nombres entiers

À l'aide du PGCD

Dès que l'un des deux entiers a ou b est non nul, leur PPCM peut être calculé en utilisant leur plus grand commun diviseur (PGCD)^[6] :

${\displaystyle \operatorname {PPCM} (a,b)={\dfrac {|ab|}{\operatorname {PGCD} (a,b)}}}$.

Ainsi, l'algorithme d'Euclide pour le calcul du PGCD permet de calculer aussi le PPCM. A titre d'exemple, calculons PGCD(60, 168) avec l'algorithme d'Euclide :
168 = 60 × 2 + 48
60 = 48 × 1 + 12
48 = 12 × 4 + 0.

Donc PGCD(60, 168) = 12 et PPCM(60, 168) = (60×168)/12 = 840.

À l'aide de la décomposition en facteurs premiers

La décomposition en facteurs premiers du PPCM de n entiers strictement positifs contient tous les nombres premiers qui apparaissent dans au moins une des décompositions en facteurs premiers de ces n entiers, chacun affecté du plus grand exposant qui apparait dans celles-ci^[10].

On obtient donc une méthode de calcul du PPCM en décomposant chaque nombre en produit de nombres premiers.

Exemple : prenons les nombres 60 et 168 et décomposons les en produits de facteurs premiers. On a :

• 60 = 2×2×3×5 = 2²×3×5 ;
• 168 = 2×2×2×3×7 = 2³×3×7.

Pour le nombre premier 2, le plus grand exposant est 3. Pour les nombres premiers 3, 5 et 7, le plus grand exposant est 1. On a ainsi PPCM(60, 168) = 2³×3×5×7 = 840

Généralisation à certains anneaux

Le concept de PPCM peut être étendu à d'autres ensembles mathématiques que celui des entiers relatifs, et notamment à certains anneaux comme les anneaux à PGCD : l'unicité et même l'existence du PPCM de deux éléments n'y sont pas garanties, mais le PPCM peut y être défini.

Dans les anneaux factoriels, qui sont des anneaux à PGCD dotés de propriétés supplémentaires, l'existence du PGCD et du PPCM de deux éléments est garantie, et leur unicité également, aux éléments inversibles près^[11]. On peut alors décomposer tout élément ${\displaystyle a}$ non nul d'un tel anneau sous la forme : ${\displaystyle a\sim \prod _{p}{p}^{v_{p}(a)}}$^[12], qui est la généralisation de la décomposition en produits de facteurs premiers d'entiers.

Et le PGCD et le PPCM de ${\displaystyle a}$ et de ${\displaystyle b}$ sont définis comme :

${\displaystyle \mathrm {PGCD} (a,b)\sim \prod _{p}{p}^{\min(v_{p}(a),v_{p}(b))}}$

${\displaystyle \mathrm {PPCM} (a,b)\sim \prod _{p}{p}^{\max(v_{p}(a),v_{p}(b))}}$

On a alors les relations suivantes :

${\displaystyle {\rm {PGCD}}(a,b)\times {\rm {PPCM}}(a,b)\sim ab}$

${\displaystyle {\rm {PPCM}}(ac,bc)\sim c\times {\rm {PPCM}}(a,b)}$