Nombres premiers et diviseurs communs

Nombres premiers

Définition Nombre premier

Un nombre premier est un entier naturel $p\ge 2$ dont les seuls diviseurs positifs sont $1$ et $p$.
Un entier naturel $n\ge 2$ qui n'est pas premier est appelé composé.

Remarques

$1$ n'est pas un nombre premier car il n'a qu'un seul diviseur positif : lui-même.
Un nombre premier $p$ est un entier naturel supérieur ou égal à $2$, soit $p \geq 2$.
À part $2$, tous les nombres premiers sont impairs.
Il y a $25$ nombres premiers strictement inférieurs à $100$ : $$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. $$
Si un entier naturel $n \geq 2$ n'est pas premier, il admet un diviseur strict $d$ tel que $1 < d < n$.

Proposition Existence d'un diviseur premier

Tout entier naturel $n \geq 2$ admet au moins un diviseur premier.

Preuve

Soit $n \geq 2$ un entier naturel.

Si $n$ est premier, alors il est son propre diviseur premier et la propriété est vraie.
Si $n$ n'est pas premier, alors il admet un diviseur $a_1$ distinct de $1$ et de $n$. Par définition, $2 \le a_1 \le n-1$, donc \(a_1
Si $a_1$ n'est pas premier, il est à son tour divisible par un entier $a_2$ tel que $2 \le a_2 < a_1$.
En poursuivant ce processus, si aucun des entiers obtenus n'était premier, on construirait une suite infinie strictement décroissante d'entiers strictement positifs $$ n > a_1 > a_2 > \cdots, $$ ce qui est impossible.

Par conséquent, l'un au moins des entiers $a_k$ est premier, et il est en outre un diviseur de $n$.

Theorem Infinité des nombres premiers

Il existe une infinité de nombres premiers.

Preuve

Supposons qu'il n'existe qu'un nombre fini de nombres premiers $p_1,\dots,p_n$ et posons $M=p_1p_2\cdots p_n+1$.
Pour tout $k$, la division euclidienne de $M$ par $p_k$ laisse le reste $1$, donc aucun $p_k$ ne divise $M$.
Cela contredit le fait que tout entier naturel $\ge 2$ admet un diviseur premier.
Donc il existe une infinité de nombres premiers.

Exercice

Démontrer que tout entier naturel $n \geq 2$ qui n'est pas premier admet un diviseur premier $p$ tel que $2 \le p \le \sqrt{n}$.
Montrer que l'entier $53$ est un nombre premier.

Correction

Démonstration du théorème :
Supposons que $n \geq 2$ soit un nombre composé. Par définition, il existe deux entiers $a$ et $b$ tels que : $$ n = a \times b \quad \text{avec} \quad 1 < a \le b < n $$ Supposons par l'absurde que $a > \sqrt{n}$ et $b > \sqrt{n}$. On aurait alors : $$ a \times b > \sqrt{n} \times \sqrt{n} \implies n > n $$ C'est impossible. Donc, on a nécessairement $a \le \sqrt{n}$.
Comme $a \ge 2$, d'après la propriété d'existence d'un diviseur premier, $a$ admet au moins un diviseur premier $p$.
Puisque $p \mid a$ et $a \le \sqrt{n}$, on en déduit que $p \le \sqrt{n}$.
Comme $p$ divise $a$ et $a$ divise $n$, alors $p$ est un diviseur premier de $n$ vérifiant la condition.
Application à $n = 53$ :
On calcule la racine carrée : $\sqrt{53} \approx 7{,}28$.
D'après le théorème, si $53$ est composé, il doit admettre un diviseur premier $p \le 7$.
Les nombres premiers inférieurs ou égaux à $7$ sont 2, 3, 5 et 7. Testons-les :
- 53 est impair, donc non divisible par 2.
- La somme des chiffres est $5+3=8$. 8 n'est pas divisible par 3, donc 53 n'est pas divisible par 3.
- 53 ne se termine ni par 0 ni par 5, donc non divisible par 5.
- $53 = 7 \times 7 + 4$. Le reste n'est pas nul, donc 53 n'est pas divisible par 7.
Puisque $53$ n'est divisible par aucun nombre premier $p \le \sqrt{53}$, 53 est un nombre premier.

Méthode Reconnaître un nombre premier

Pour déterminer si un entier naturel $n \geq 2$ est premier, on limite la recherche de diviseurs grâce à la propriété suivante : Un entier naturel $n \geq 2$ est composé si et seulement s'il admet au moins un diviseur premier $p$ tel que $2 \le p \le \sqrt{n}$.Étapes à suivre :

Calculer la valeur approchée de $\sqrt{n}$.
Lister tous les nombres premiers $p$ contenus dans l'intervalle $[2, \sqrt{n}]$.
Tester la divisibilité de $n$ par chacun de ces nombres premiers.
- Si aucun de ces nombres ne divise $n$, alors $n$ est premier.
- Si au moins l'un d'entre eux divise $n$, alors $n$ est composé.

Exemple

167 est-il un nombre premier ?

Correction

$\sqrt{167} \approx 12{,}9$.
Les nombres premiers à tester sont : 2, 3, 5, 7 et 11.
Tests de divisibilité :
- 167 est impair (non divisible par 2).
- $1+6+7 = 14$ (non divisible par 3).
- 167 ne finit ni par 0 ni par 5 (non divisible par 5).
- $167 = 7 \times 23 + 6$ (non divisible par 7).
- $167 = 11 \times 15 + 2$ (non divisible par 11).
Puisqu'aucun nombre premier $p \leq \sqrt{167}$ ne divise 167, 167 est un nombre premier.

Factorisation en nombres premiers

Theorem Décomposition en facteurs premiers

Tout entier naturel $n\ge 2$ s'écrit$$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},$$où $p_1,\dots,p_k$ sont des nombres premiers distincts et $\alpha_1,\dots,\alpha_k$ des entiers naturels non nuls.
Cette décomposition est unique à l'ordre des facteurs près.

Preuve

Existence (par récurrence forte) :
Soit $P(n)$ la propriété : « L'entier $n$ admet une décomposition en facteurs premiers. »
- Initialisation : Pour $n=2$. L'entier $2$ étant premier, il se décompose en lui-même. Donc $P(2)$ est vraie.
- Hérédité : Soit $n \geq 2$. On suppose que tout entier $k$ tel que $2 \leq k \leq n$ admet une décomposition en facteurs premiers. Montrons qu'il en est de même pour $n+1$.
  - Si $n+1$ est premier, il se décompose en lui-même.
  - Si $n+1$ est composé, il admet un diviseur strict $d$ tel que $2 \leq d \leq n$. On peut écrire $n+1 = dq$ avec $q\ge 2$. Comme $d \geq 2$, on a $q \leq n$. D'après l'hypothèse de récurrence, $d$ et $q$ se décomposent en facteurs premiers, donc $n+1$ aussi.
- Conclusion : Par principe de récurrence forte, tout entier $n \geq 2$ admet une décomposition en facteurs premiers.
Unicité :
Supposons qu'un entier $n$ possède deux décompositions :$$n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m,$$où tous les $p_i$ et $q_j$ sont des nombres premiers.
Comme $p_1$ est premier et divise le produit $q_1 q_2 \cdots q_m$, le théorème de Gauss implique que $p_1$ divise l'un des facteurs $q_j$. Comme $q_j$ est premier, on a nécessairement $p_1=q_j$. En simplifiant par ce facteur commun et en itérant le raisonnement, on conclut que les facteurs premiers sont les mêmes, à l'ordre près.
Note : Cette partie est admise pour le moment car elle repose sur le théorème de Gauss qui sera vu plus tard.

Méthode Arbre de facteurs

La méthode de l'arbre de facteurs consiste à décomposer un nombre composé en facteurs plus petits, puis à continuer à décomposer ces facteurs jusqu'à ce qu'il ne reste plus que des facteurs premiers.

Place le nombre en haut de l'arbre de facteurs.
Vérifie si le nombre est premier.
1. Si le nombre est premier : Entoure-le. Tu as terminé pour cette branche.
2. Si le nombre est composé : Décompose-le en deux facteurs plus petits. Écris ces deux facteurs comme des branches en dessous du nombre. Répète l'étape 2 pour chacun de ces nouveaux facteurs.
La factorisation en nombres premiers est le produit de tous les nombres premiers entourés dans l'arbre.

Exemple

Trouve une factorisation en nombres premiers de $24$.

Correction

Étape 1 :
Étape 2 : $24$ est un nombre composé. $24 = 2 \times 12$.
Étape 3 : $12$ est un nombre composé. $12 = 2 \times 6$.
Étape 4 : $6$ est un nombre composé. $6 = 2 \times 3$.

Une factorisation en nombres premiers est $24 = 2^3 \times 3$.

Plus grand commun diviseur (PGCD)

Proposition Existence du PGCD

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls. L'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément.

Preuve

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.

L'ensemble des diviseurs d'un entier non nul est fini. Comme au moins l'un des deux entiers $a$ ou $b$ est non nul, au moins l'un des deux ensembles de diviseurs est fini, donc leur intersection (l'ensemble des diviseurs communs) est finie.
L'ensemble des diviseurs communs n'est pas vide car $1$ divise $a$ et $b$.
Or tout sous-ensemble fini non vide de $\mathbb{N}$ admet un plus grand élément. Donc l'ensemble des diviseurs communs admet un plus grand élément.

Définition Plus grand commun diviseur (PGCD)

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls. Le plus grand élément de l'ensemble des diviseurs communs positifs de $a$ et $b$ est appelé le plus grand commun diviseur. On le note $PGCD(a,b)$.

Exemple

$PGCD(24,18)=6$.

Proposition Propriétés du PGCD

Soient $a$ et $b$ des entiers relatifs non nuls.

Si $b$ divise $a$, alors $PGCD(a,b)=|b|$.
Pour tout entier relatif $k$, $PGCD(a,b)=PGCD(a-kb,b)$.
Si \(0

Méthode Algorithme d'Euclide

Soient $a$ et $b$ deux entiers tels que $0 < b \leq a$. Alors, l'algorithme suivant permet de calculer, en un nombre fini d'étapes, le PGCD de $a$ et $b$ :

Calculer le reste $r$ dans la division euclidienne de $a$ par $b$.
Tant que $r \neq 0$ faire :
- $a \leftarrow b$,
- $b \leftarrow r$,
- calculer le nouveau reste $r$ de la division euclidienne de $a$ par $b$.
Fin du tant que
$PGCD(a,b)=b$.

Exemple

Calculer $PGCD(1554,136)$ à l'aide de l'algorithme d'Euclide.

Correction

$$\begin{aligned}1554 &= 136\times 11 + 58,\\ 136 &= 58\times 2 + 20,\\ 58 &= 20\times 2 + 18,\\ 20 &= 18\times 1 + 2,\\ 18 &= 2\times 9 + 0.\end{aligned}$$Le dernier reste non nul est $2$, donc $PGCD(1554,136)=2$.

Méthode Calculer le PGCD par la décomposition en facteurs premiers

Pour trouver le PGCD de deux entiers $a$ et $b$ à l'aide de leurs décompositions en facteurs premiers, on suit les étapes suivantes :

Décomposer les deux nombres $a$ et $b$ en produits de facteurs premiers.
Identifier les facteurs premiers communs aux deux décompositions.
Pour chaque facteur premier commun, retenir la puissance avec le plus petit exposant présent dans les deux décompositions.
Le PGCD est le produit de ces facteurs premiers communs élevés à leurs plus petits exposants respectifs.

Exemple

Trouver $PGCD(120, 84)$ en utilisant la décomposition en facteurs premiers.

Correction

On décompose les deux nombres : $$ \begin{aligned} 120 &= 2^3 \times 3^1 \times 5^1 \\ 84 &= 2^2 \times 3^1 \times 7^1 \end{aligned} $$
Les facteurs premiers communs sont 2 et 3.
On choisit les plus petits exposants :
- Pour le facteur 2 : les exposants sont 3 et 2. Le plus petit est 2.
- Pour le facteur 3 : les exposants sont 1 et 1. Le plus petit est 1.
On calcule le produit : $$ PGCD(120, 84) = 2^2 \times 3^1 = 4 \times 3 = \mathbf{12} $$

Définition Nombres premiers entre eux

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.
On dit que $a$ et $b$ sont premiers entre eux si $PGCD(a,b)=1$.

Exemple

$PGCD(15,8)=1$, donc $15$ et $8$ sont premiers entre eux.
Pour tout entier relatif $a$, $PGCD(a,1)=1$, donc $1$ est premier avec tout entier.

Remarques

Il ne faut pas confondre nombres premiers entre eux et nombres premiers. Les entiers $15$ et $8$ sont premiers entre eux mais ni l'un ni l'autre n'est premier. En revanche, deux nombres premiers distincts sont toujours premiers entre eux.
Une fraction irréductible $q$ s'écrit comme le rapport de deux entiers premiers entre eux : $$ q=\frac{a}{b} \quad \text{avec } a\in\mathbb{Z},\ b\in\mathbb{N}^*,\ \text{et } PGCD(a,b)=1. $$

Plus petit commun multiple (PPCM)

Proposition Existence du PPCM

Soient $a$ et $b$ deux entiers relatifs non nuls. L'ensemble des multiples communs strictement positifs de $a$ et $b$ est une partie non vide de $\mathbb{N}^*$ ; elle admet donc un plus petit élément.

Définition Plus petit commun multiple

Soient $a$ et $b$ deux entiers relatifs non nuls. Le plus petit entier naturel strictement positif qui est un multiple commun à $a$ et $b$ est appelé le plus petit commun multiple.
On le note $PPCM(a, b)$ ou $a \lor b$.

Proposition Relation entre PGCD et PPCM

Soient $a$ et $b$ deux entiers naturels non nuls. On a :$$ PGCD(a, b) \times PPCM(a, b) = a \times b $$De manière plus générale, pour tous entiers relatifs non nuls $a, b \in \mathbb{Z}$ :$$ PGCD(a, b) \times PPCM(a, b) = |ab| $$

Preuve

Soit $d = PGCD(a, b)$. Il existe des entiers $a'$ et $b'$ premiers entre eux tels que $a = da'$ et $b = db'$.
Soit $m$ un multiple commun de $a$ et $b$.

Comme $m$ est multiple de $a$, il existe un entier $k$ tel que $m = ka = kda'$.
Comme $m$ est aussi multiple de $b$, on a $b \mid kda'$, soit $db' \mid kda'$.
En simplifiant par $d$, on obtient $b' \mid ka'$.
Comme $PGCD(a', b') = 1$, d'après le théorème de Gauss, $b'$ divise $k$.
La plus petite valeur strictement positive de $k$ est donc $k = b'$.

Le plus petit multiple commun est donc :$$ PPCM(a, b) = b' \times a = b' \times (da') = d \times a' \times b' $$On vérifie le produit :$$ PGCD(a, b) \times PPCM(a, b) = d \times (d a' b') = (da') \times (db') = a \times b $$

Méthode PPCM par la décomposition en facteurs premiers

Pour déterminer le PPCM de deux entiers $a$ et $b$ :

Écrire la décomposition en facteurs premiers de $a$ et de $b$.
Identifier tous les facteurs premiers apparaissant dans au moins une des décompositions.
Pour chacun de ces facteurs, retenir le plus grand exposant observé.
Le PPCM est le produit de ces facteurs élevés à leurs plus grands exposants respectifs.

Exemple

Calculer $PPCM(120, 84)$.

Correction

Par décomposition en facteurs premiers :$$\begin{aligned}120 &= 2^3 \times 3^1 \times 5^1 \\ 84 &= 2^2 \times 3^1 \times 7^1\end{aligned}$$On prend la puissance maximale pour chaque facteur $\{2, 3, 5, 7\}$ :$$ PPCM(120, 84) = 2^3 \times 3^1 \times 5^1 \times 7^1 = 8 \times 3 \times 5 \times 7 = \mathbf{840} $$Vérification par le PGCD : $PGCD(120, 84) = 2^2 \times 3^1 = 12$ et $12 \times 840 = 120 \times 84$.