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].

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
modifierDéfinition et existence
modifierLa 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 :
Cette définition peut être étendue à un nombre quelconques d'entiers, avec, par exemple pour trois entiers a, b, c :
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
modifierSoient a, b, c trois entiers naturels.
- [5]
- [5]
- les multiples communs à a et b sont les multiples de [6]; en particulier :
- [6]
- pour [5]
- , 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
modifierLe PPCM et le plus grand commun diviseur (PGCD) de nombres entiers sont reliés par plusieurs formules, notamment :
- [7]
- .
PPCM et facteurs premiers
modifierD'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 et sont deux entiers, et , …, sont les nombres premiers, rangés en ordre croissant, qui divisent ou , la décomposition de en produit de facteurs premiers est de la forme ….. = [8]. De même, celle de est de la forme . Alors [9]: .
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
modifierÀ l'aide du PGCD
modifierDè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] :
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
modifierLa 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 = 22×3×5 ;
- 168 = 2×2×2×3×7 = 23×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) = 23×3×5×7 = 840
Généralisation à certains anneaux
modifierLe 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 non nul d'un tel anneau sous la forme : [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 et de sont définis comme :
On a alors les relations suivantes :
Notes et références
modifier- ↑ Cette notation, utilisée plus généralement pour la borne supérieure dans les treillis ici celui de la divisibilité, sert également pour la disjonction logique.
- ↑ La notation correspondante pour le PGCD est (a, b).
- ↑ Burat 1891, p. 89-90.
- ↑ La démonstration formelle de l'existence de ce plus petit entier dépasse le cadre de cet article.
- Ces trois propriétés constituent une caractérisation fonctionnelle du PPCM.
- Pour une démonstration, voir par exemple « PPCM » sur Wikiversité (voir infra).
- ↑ Burat 1891, p. 92-93.
- ↑ Le nombre de fois que l'entier premier p apparait dans cette écriture s'appelle la valuation p-adique de n, notée vp(n). Un entier non nul m divise n si et seulement si pour tout p, vp(m) ≤ vp(n).
- ↑ Stillwell 1998, p. 20-21.
- ↑ Burat 1891, p. 90-91.
- ↑ Thomas Bertin, « Leçon 142 : PGCD et PPCM, algorithmes de calcul. Applications. » [PDF],
- ↑ Dans un anneau factoriel, veut dire qu'il existe un élément inversible de l'anneau tel que .
Bibliographie
modifier- E. Burat, Traité d'arithmétique, Paris, Belin Frères, , 377 p. (lire en ligne).
- (en) John Stillwell, Numbers and Geometry, New York, Springer, , 368 p. (ISBN 0-387-98289-2, lire en ligne).
Voir aussi
modifierArticles connexes
modifier- Livre VII des Éléments d'Euclide
- Treillis (ensemble ordonné)
- Décomposition en produit de facteurs premiers