Nombres premiers et décomposition

6.1 Nombres premiers

Définition. Un entier naturel $p$ est premier s'il a exactement deux diviseurs positifs : $1$ et lui-même. Ainsi $0$ et $1$ ne sont pas premiers.

Les nombres premiers inférieurs à $50$ sont : $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$.

Propriété. Tout entier $n \geq 2$ a au moins un diviseur premier : son plus petit diviseur supérieur ou égal à $2$. Si de plus $n$ n'est pas premier, il a un diviseur premier $p$ tel que $p^2 \leq n$.

Démonstration. Soit $p$ le plus petit diviseur de $n$ supérieur ou égal à $2$. Si $p$ n'était pas premier, il aurait un diviseur $d$ avec $2 \leq d < p$, qui diviserait aussi $n$ : impossible. Si $n$ n'est pas premier, $n = p\,m$ avec $m \geq p$ (car $m$ est aussi un diviseur de $n$ supérieur ou égal à $2$), donc $n \geq p^2$.

Méthode : test de primalité. Un entier $n \geq 2$ est premier si, et seulement si, il n'est divisible par aucun nombre premier $p$ tel que $p \leq \sqrt{n}$.

Exemple 28.

• $211$ : $\sqrt{211} \approx 14{,}5$. $211$ n'est divisible ni par $2$, ni par $3$, ni par $5$, ni par $7$, ni par $11$, ni par $13$ : il est premier.
• $221$ : $\sqrt{221} \approx 14{,}9$, et $221 = 13 \times 17$ : il n'est pas premier.

Propriété. Soit $p$ un nombre premier.

• Si $p$ ne divise pas un entier $a$, alors $p$ et $a$ sont premiers entre eux (le seul diviseur positif commun possible est $1$).
• Si $p$ divise un produit $a\,b$, alors $p$ divise $a$ ou $p$ divise $b$.

Démonstration du second point. Si $p$ ne divise pas $a$, il est premier avec $a$ ; comme il divise $a\,b$, le théorème de Gauss donne $p \mid b$.

Complément. Il existe une infinité de nombres premiers. En effet, si $p_1$, $p_2$, …, $p_k$ étaient tous les nombres premiers, l'entier $N = p_1\,p_2 \cdots p_k + 1$ aurait un diviseur premier $p_i$ ; $p_i$ diviserait alors $N - p_1 p_2 \cdots p_k = 1$, ce qui est impossible.

6.2 Décomposition en produit de facteurs premiers

Théorème (admis). Tout entier $n \geq 2$ s'écrit comme un produit de nombres premiers : $n = p_1^{\alpha_1}\,p_2^{\alpha_2} \cdots p_k^{\alpha_k},$ où $p_1 < p_2 < \dots < p_k$ sont des nombres premiers et $\alpha_1$, …, $\alpha_k$ des entiers naturels non nuls. Cette écriture est unique.

Méthode. On divise par $2$ autant de fois que possible, puis par $3$, par $5$, par $7$, et ainsi de suite, jusqu'à obtenir $1$.

Exemple 29.

$2\,520$	$2$
$1\,260$	$2$
$630$	$2$
$315$	$3$
$105$	$3$
$35$	$5$
$7$	$7$
$1$

Donc $2\,520 = 2^3 \times 3^2 \times 5 \times 7$. De même, $924 = 2^2 \times 3 \times 7 \times 11$ et $360 = 2^3 \times 3^2 \times 5$.

Conséquence : les diviseurs. Les diviseurs positifs de $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ sont les entiers $p_1^{\beta_1} \cdots p_k^{\beta_k}$ avec $0 \leq \beta_i \leq \alpha_i$ pour chaque $i$. Il y en a $(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$. Par exemple, $2\,520$ a $4 \times 3 \times 2 \times 2 = 48$ diviseurs positifs.

6.3 PGCD par la décomposition

Méthode. On décompose les entiers en facteurs premiers. Le PGCD est le produit des facteurs premiers communs, chacun avec le plus petit exposant. Cette méthode vaut aussi pour plusieurs entiers.

Exemple 30. $924 = 2^2 \times 3 \times 7 \times 11$ et $360 = 2^3 \times 3^2 \times 5$. Les facteurs communs sont $2$ et $3$ ; on prend $2^2$ et $3^1$ : $\mathrm{PGCD}(924\,;360) = 2^2 \times 3 = 12$. On retrouve le résultat de l'algorithme d'Euclide.

Exemple 31. $12 = 2^2 \times 3$, $18 = 2 \times 3^2$ et $30 = 2 \times 3 \times 5$, donc $\mathrm{PGCD}(12\,;18\,;30) = 2 \times 3 = 6$.