Plus petit commun multiple

Plus petit commun multiple

En mathématiques et plus précisément en arithmétique, le plus petit commun multiple – en abrégé PPCM – de deux entiers non nuls a et b est le plus petit entier strictement positif qui soit à la fois multiple de ces deux nombres. On le note a ∨ b[1] ou PPCM(a, b).

Le PPCM de a et b peut également se définir 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.

Le PPCM peut se définir plus généralement pour un nombre quelconque d'éléments : par exemple le PPCM de n entiers non nuls est le plus petit entier strictement positif multiple simultanément de ces n entiers.

Sommaire

Définition

Soient a et b deux entiers relatifs.

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

Calcul

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

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

À l'aide du PGCD

Dans le cas où aucun des deux entiers a et b n'est nul, le plus petit commun multiple peut être calculé en utilisant le plus grand commun diviseur (ou PGCD) de a et b :

a\vee b=\dfrac{|a b|}{a\wedge b}, ce qui s'écrit aussi \operatorname{PPCM}(a,b)=\dfrac{|a b|}{\operatorname{PGCD}(a,b)}.

Démonstration

Supposons, sans perte de généralité, que les entiers a et b sont strictement positifs, et définissons les entiers d,a',b',m par :

d=\mathrm{PGCD}(a,b),~a=da',~b=db',~m=\mathrm{PPCM}(a,b).
  • m est un multiple commun à a et b, donc il existe un entier k tel que m = bk et a | bk, soit (en divisant par d) : a' | b'k. Comme a' et b' sont premiers entre eux, en vertu du lemme de Gauss on obtient : a' | k, soit (en multipliant par b) : da'b' | m.
  • da'b' = a'b = ab' est un multiple commun strictement positif de a et b, donc il est minoré par m.
  • Des deux points précédent on déduit que m = da'b', soit : m = ab / d.

Ainsi, l'algorithme d'Euclide pour le calcul du PGCD nous donne aussi un algorithme de calcul du PPCM.

Exemple.

Avec l'algorithme d'Euclide, calculons PGCD(60,168) :
168 = 60 × 2 + 48
60 = 48 x 1 + 12
48 = 12 × 4 + 0.

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

Notes et références

  1. ↑ 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.

Article connexe

Livre VII des Éléments d'Euclide


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Plus petit commun multiple de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Plus grand commun diviseur (mathematiques elementaires) — Plus grand commun diviseur (mathématiques élémentaires) Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Plus grand commun diviseur (mathématiques élémentaires) — Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Plus grand commun diviseur — Pour une introduction à cette notion, consulter l article : PGCD de nombres entiers. En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui… …   Wikipédia en Français

  • multiple — [ myltipl ] adj. et n. m. • 1572 math.; multiplice 1380; lat. multiplex 1 ♦ Qui n est pas simple. Qui est composé de plusieurs éléments de nature différente, ou qui se manifeste sous des formes différentes. ⇒ divers. « Ce vaste et multiple monde… …   Encyclopédie Universelle

  • commun — commun, une [ kɔmœ̃, yn ] adj. et n. m. • 842; lat. communis I ♦ Adj. 1 ♦ (XIIe) Qui appartient, qui s applique à plusieurs personnes ou choses. Ces choses ont un usage commun. Un puits, un passage commun. Terres communes (⇒ communal) . Maison… …   Encyclopédie Universelle

  • Plus haut facteur commun — Plus grand commun diviseur En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers. Par exemple le PGCD de 42… …   Wikipédia en Français

  • PPCM — Plus Petit Commun Multiple …   Sigles et Acronymes francais

  • PPCM — Plus petit commun multiple En mathématiques et plus précisément en arithmétique, le plus petit commun multiple, en abrégé PPCM (noté lcm en anglais pour least common multiple), de deux entiers naturels a et b, est le plus petit entier qui soit à… …   Wikipédia en Français

  • PPCM (mathématiques élémentaires) — Plus petit commun multiple En mathématiques et plus précisément en arithmétique, le plus petit commun multiple, en abrégé PPCM (noté lcm en anglais pour least common multiple), de deux entiers naturels a et b, est le plus petit entier qui soit à… …   Wikipédia en Français

  • Ppcm — Plus petit commun multiple En mathématiques et plus précisément en arithmétique, le plus petit commun multiple, en abrégé PPCM (noté lcm en anglais pour least common multiple), de deux entiers naturels a et b, est le plus petit entier qui soit à… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”