PPCM et petit théorème de Fermat

7.1 PPCM

Définition. Soit $a$ et $b$ deux entiers non nuls. Le plus petit commun multiple de $a$ et $b$ est le plus petit entier strictement positif qui est à la fois multiple de $a$ et de $b$. On le note $\mathrm{PPCM}(a\,;b)$, ou $a \vee b$. On définit de même le PPCM de plusieurs entiers non nuls.

Exemple 32. Les multiples positifs de $12$ sont $12$, $24$, $36$, $48$… ; ceux de $18$ sont $18$, $36$, $54$… Le premier multiple commun est $36$ : $\mathrm{PPCM}(12\,;18) = 36$.

Propriété. Les multiples communs de $a$ et $b$ sont exactement les multiples de $\mathrm{PPCM}(a\,;b)$.

Démonstration. Notons $m = \mathrm{PPCM}(a\,;b)$. Tout multiple de $m$ est un multiple de $a$ et de $b$. Réciproquement, soit $M$ un multiple commun de $a$ et $b$ ; la division euclidienne donne $M = m\,q + r$ avec $0 \leq r < m$. Alors $r = M - m\,q$ est aussi un multiple commun de $a$ et $b$. Comme $r < m$ et que $m$ est le plus petit multiple commun strictement positif, $r = 0$ : $M$ est un multiple de $m$.

7.2 PPCM par la décomposition

Méthode. Le PPCM est le produit de tous les facteurs premiers qui apparaissent dans les décompositions, chacun avec le plus grand exposant. Cette méthode vaut pour plusieurs entiers.

Exemple 33. $924 = 2^2 \times 3 \times 7 \times 11$ et $360 = 2^3 \times 3^2 \times 5$, donc $\mathrm{PPCM}(924\,;360) = 2^3 \times 3^2 \times 5 \times 7 \times 11 = 27\,720$.

Propriété. Pour deux entiers naturels non nuls $a$ et $b$ : $\mathrm{PGCD}(a\,;b) \times \mathrm{PPCM}(a\,;b) = a \times b.$

Justification. Pour chaque nombre premier, le plus petit et le plus grand des deux exposants ont pour somme la somme des deux exposants. Vérification : $12 \times 27\,720 = 332\,640 = 924 \times 360$.

Attention : cette égalité n'est vraie que pour deux entiers.

Exemple 34 (situation simplifiée). À une gare routière, trois lignes de cars partent respectivement toutes les $12$, $18$ et $30$ minutes. Les trois cars sont partis ensemble à $6$ h. À quelle heure repartiront-ils ensemble pour la première fois ?

Le temps cherché, en minutes, est un multiple commun de $12 = 2^2 \times 3$, $18 = 2 \times 3^2$ et $30 = 2 \times 3 \times 5$ : le plus petit est $\mathrm{PPCM}(12\,;18\,;30) = 2^2 \times 3^2 \times 5 = 180$. Ils repartiront ensemble $180$ minutes plus tard, soit à $9$ h.

7.3 Petit théorème de Fermat

Théorème (petit théorème de Fermat, admis). Soit $p$ un nombre premier. Pour tout entier naturel non nul $x$ : $x^p \equiv x \;[p].$

C'est la forme donnée par le programme, qui indique qu'« on pourra utiliser » ce théorème.

Conséquence. Si de plus $p$ ne divise pas $x$, alors $x^{p-1} \equiv 1 \;[p].$

Démonstration. $p$ divise $x^p - x = x\,(x^{p-1} - 1)$. Comme $p$ ne divise pas $x$, $p$ est premier avec $x$ ; d'après le théorème de Gauss, $p$ divise $x^{p-1} - 1$.

Exemple 35. Reste de $3^{2\,026}$ dans la division par $7$.

$7$ est premier et ne divise pas $3$, donc $3^6 \equiv 1 \;[7]$. On divise l'exposant par $6$ : $2\,026 = 6 \times 337 + 4$. Donc $3^{2\,026} = (3^6)^{337} \times 3^4 \equiv 1 \times 81 \;[7], \qquad 81 = 7 \times 11 + 4.$ Le reste est $4$.

Exemple 36. Pour tout entier naturel non nul $n$, $n^5 - n$ est divisible par $5$ : c'est le petit théorème de Fermat avec $p = 5$. On a aussi $2^{100} \equiv 2 \;[7]$ (exemple 10) : le petit théorème de Fermat donne $2^6 \equiv 1 \;[7]$, et $100 = 6 \times 16 + 4$, donc $2^{100} \equiv 2^4 = 16 \equiv 2 \;[7]$.