francebalade.fr Cours de Mathématiques Table des matières Votre avis sur ce site

Le plus petit commun multiple

Quand deux régularités finissent-elles par retomber d'accord ?

Le PPCM de deux entiers est le plus petit nombre qu'ils divisent tous les deux. On peut le chercher en avançant de multiple en multiple jusqu'à la première rencontre ; le déduire du PGCD, car le produit des deux nombres vaut toujours PGCD × PPCM ; ou le lire directement sur les décompositions en facteurs premiers. Ces trois routes mènent au même endroit, et la deuxième est la seule praticable sur de grands nombres.

a b

Planche 1 Deux sauteurs qui cherchent à se rejoindre

Un premier sauteur avance de a en a, le second de b en b. À chaque tour, on fait sauter celui qui est en retard. Ils finissent forcément par tomber sur la même case : cette case est le PPCM.

Vitesse 4 / s

sauteur bleu (multiples de a)

—

sauteur violet (multiples de b)

—

sauts effectués

sauts nécessaires

—

rencontre

—

multiples de a multiples de b multiple commun

—

Planche 2 a × b = PGCD × PPCM

Voici pourquoi. Découpons le rectangle a × b en bandes horizontales de hauteur d = PGCD : il y en a exactement b / d, toutes de format a × d. Mises bout à bout, elles forment un rectangle de hauteur d et de largeur a × b / d — qui est précisément le PPCM.

avancement

d = PGCD

—

nombre de bandes b / d

—

largeur obtenue

—

a × b

—

d × PPCM

—

écart

—

Planche 3 Sur les facteurs premiers : max d'un côté, min de l'autre

Décomposons a et b. Pour chaque nombre premier, le PPCM prend le plus grand des deux exposants — il faut être multiple des deux — tandis que le PGCD prend le plus petit. Les deux exposants d'un même premier étant toujours l'un le max et l'autre le min, leur somme est conservée : c'est la planche 2, autrement dite.

—

PPCM (max des exposants)

—

PGCD (min des exposants)

—

contrôle max + min = somme

—

exposant dans a exposant dans b retenu pour le PPCM

Cette méthode est la plus parlante et la plus mauvaise en pratique : elle exige de factoriser, ce que personne ne sait faire vite sur de grands nombres. La bonne méthode reste PPCM = (a ÷ PGCD) × b, où le PGCD s'obtient par l'algorithme d'Euclide en quelques divisions. On divise avant de multiplier, pour ne pas fabriquer inutilement un produit géant.

Planche 4 Deux engrenages qui se retrouvent

C'est la situation où le PPCM se voit. Deux roues dentées engrenées : une dent marquée sur la petite roue, une encoche marquée sur la grande. Elles ne se retrouvent face à face qu'au bout d'un nombre de dents égal au PPCM des deux dentures.

roue A 8 dents roue B 12 dents vitesse

dents défilées

tours de A

tours de B

PPCM des dentures

—

retour à la position initiale

—

coïncidences observées

L'autre usage quotidien : le dénominateur commun

Additionner deux fractions, c'est chercher le PPCM des dénominateurs — le plus petit dénominateur qui convienne aux deux.

1/a + 1/b, avec les nombres du bandeau

—

Prendre a × b comme dénominateur commun marche toujours, mais oblige à simplifier ensuite. Le PPCM est exactement le dénominateur qui évite ce travail.

Planche 5 — signature Le PPCM des cent premiers entiers

A. Un escalier qui suit la droite y = n

Posons L(n) = PPCM(1, 2, …, n). Ce nombre explose : L(20) vaut déjà 232 792 560. Traçons non pas L(n) mais son logarithme. L'escalier obtenu — la fonction ψ de Tchebychev — colle à la droite y = n, et cette coïncidence est le théorème des nombres premiers.

n ≤

ln L(n) au bout

—

rapport ln L(n) / n

—

nombre de marches

—

chiffres de L(n)

—

contrôle BigInt − somme des ln p

—

valeurs exactes

—

Chaque marche a lieu à une puissance de nombre premier, et sa hauteur vaut ln p. L'escalier ne monte donc que lorsqu'un premier apparaît pour la première fois — ou revient à une puissance supérieure : 4, 8, 9, 16, 25, 27… Que la hauteur cumulée suive n, c'est dire que les premiers se raréfient exactement au rythme 1 / ln x. Multiplier tous les entiers jusqu'à n donne n! ; ne garder que ce qui est nécessaire pour être divisible par chacun donne un nombre de la taille de eⁿ, immensément plus petit.

B. Quand le PPCM est-il aussi grand que possible ?

PPCM(a, b) vaut au plus a × b, et cette valeur maximale est atteinte exactement quand les deux nombres n'ont aucun facteur commun. Comptons la proportion de tels couples dans un carré N × N.

N ≤

couples où PPCM = a × b

—

proportion mesurée

—

6 / π²

—

écart

—

PPCM moyen ÷ (a × b) moyen

—

Trois couples sur cinq, un peu moins : la probabilité vaut 6 / π² = 0,607927…, la même constante que pour deux entiers premiers entre eux, puisque c'est la même condition. Dans les deux cas de figure elle vient du produit ∏ (1 − 1/p²) = 1 / ζ(2), et ζ(2) = π² / 6.

Pour finir Les trois méthodes

méthode	principe	coût
Les deux sauteurs	avancer celui qui est en retard	a/d + b/d − 1 sauts — long si le PGCD est petit
Facteurs premiers	max des exposants premier par premier	exige de factoriser : impraticable en grand
Par le PGCD	PPCM = (a ÷ PGCD) × b	quelques divisions d'Euclide, toujours