Cours : Nombres premiers

Définitions et propriétés des nombres premiers

Définitions

Astuce

Par convention, dans ce cours nous n’utiliserons que des nombres dont les diviseurs et les multiples sont des entiers naturels.

Définition

Nombre premier :

Un nombre entier est dit premier s’il admet exactement deux diviseurs positifs : 1 et lui-même.

Exemple

Les nombres $2$, $3$ et $5$ sont des nombres premiers. Le nombre $8$ n’est pas un nombre premier car il est divisible par $1$, $2$, $4$ et $8$.

L’entier naturel $1$ n’est pas un nombre premier car il n’admet qu’un seul diviseur positif : $1$.

Propriétés

Propriété

Tout nombre entier $a$ strictement supérieur à $1$ admet un diviseur premier.

Démonstration

Si $a$ est premier, alors le diviseur premier cherché est $a$.

Si $a$ n’est pas premier, alors, par définition, il admet au moins un diviseur strict. Notons $\text D(a)$ l’ensemble de ses diviseurs de $a$ ; $\text D(a)=\lbrace 1\ ;\ d_1\ ;\ d_2\ ;\ …\ ;\ a\rbrace$ avec $1 < d_1 < d_2 < … < a$.

Prouvons par l’absurde que le plus petit diviseur strict de $a$, soit $d_1$, est un nombre premier.

Supposons donc que $d_1$ est non premier. Alors $d_1$ admet au moins un diviseur strict $d$ : $1 < d < d_1$.

Il en résulterait que $d$ divise $d_1$, et $d_1$ divise a donc $d$ est un diviseur strict de $a$ strictement inférieur à $d_1$ ce qui est impossible.

• Donc $d_1$ est premier.

Propriété

Tout nombre entier $a$ non premier et strictement supérieur à $1$ admet un diviseur strict inférieur ou égal à $\sqrt a$.

Démonstration

Soit $a$ un entier non premier strictement supérieur à $1$ ; on appelle $d$ le plus petit diviseur de $a$ tel que $1 < d < a$.

D’après la propriété précédente, $d$ est un nombre premier. De plus, il existe un entier $k$ tel que $n=d\times k$.

Ainsi, $k$ est un diviseur de $a$ supérieur ou égal à $d$ d’où $n=d\times k ≥d\times d$.

$n≥d^2$ donc $\sqrt n≥d$.

À retenir

Ce résultat est utile lorsqu’on veut prouver qu’un nombre $a$ est premier : il suffit de vérifier qu’il n’a pas de diviseur strict inférieur ou égal à $\sqrt a$.

Propriété

Il existe une infinité de nombres premiers.

On pourra remarquer qu’ainsi, il n’existe pas de « plus grand nombre premier » : pour tout nombre premier $p$, il existe un nombre premier $q$ strictement supérieur à $p$.

Ce théorème se démontre par l’absurde. Supposons donc qu’il n’existe qu’un nombre fini de nombres premiers : $2 < 3 < 5 < … < p$.

Posons $\text N=(2\times3\times…\times p)+1$. Le nombre $\text N$ est strictement supérieur à $1$. Il admet donc un diviseur premier $d$.

Comme les nombres $2$, $3$, $5$ jusqu’à $p$ sont les seuls nombres premiers, $d$ est nécessairement l’un de ces nombres. Le nombre $d$ divise donc le produit $2\times3\times4\times5$ et ainsi de suite jusqu’à $p$.

Mais $d$ divise également le nombre $\text N$ : il divise donc leur différence $1$, ce qui est impossible. Il existe donc une infinité de nombres premiers.

Critères de divisibilité en base 10

Soit le nombre $n=\overline{x_px_{p-1}…x_1x_0}^{10}$ dans $n$, $ x_0$ est le chiffre des unités, $x_1$ le chiffre des dizaines, etc.

Critère de divisibilité par 2

On a $n=\overline{x_px_{p-1}…x_1}\times10+x_0$ or $10≡0\ [2]$ donc $n≡x_0\ [2]$.

Propriété

Il en résulte que $n$ est divisible par $2$ si, et seulement si, son chiffre des unités est divisible par $2$, c’est-à-dire s’il se termine par $0$, $2$, $4$, $6$ ou $8$.

Critère de divisibilité par 3

On a $n=x_p10^p+x_{p-1}10^{p-1}+…+x_110^1+x_0$ or $10≡1\ [3] $ donc, pour tout entier naturel $k$, $10k≡1\ [3]$.

Ainsi, $n≡x_p+x_{p-1}+…+x_1+x_0\ [3]$.

Propriété

Il en résulte que $n$ est divisible par $3$ si et seulement si la somme de ses chiffres est divisible par $3$.

Critère de divisibilité par 4

Propriété

Un entier naturel est divisible par $4$ si et seulement si le nombre formé avec ses deux derniers chiffres est divisible par $4$.

Critère de divisibilité par 5

On a $n=\overline{x_px_{p-1}…x_1}\times10+x_0$ or $10≡0\ [5]$ donc $n≡x_0\ [5]$.

Propriété

Il en résulte que $n$ est divisible par $5$ si, et seulement si, son chiffre des unités est divisible par $5$, c’est-à-dire s’il se termine par $0$ ou $5$.

Critère de divisibilité par 9

On a $n=x_p10^p+x_{p-1}10^{p-1}+…+x_110^1+x_0$ or $10≡1\ [9]$ donc, pour tout entier $k$, $10^k≡1^k\ [9]$ soit $10^k≡1\ [9]$. Ainsi, $n≡x_p+x_{p-1}+…+x_1+x_0\ [9]$.

Propriété

Il en résulte que $n$ est divisible par $9$ si et seulement si la somme de ses chiffres est divisible par $9$.

Critère de divisibilité par 10

On a $n=\overline{x_px_{p-1}…x_1}\times10+x_0$ donc $n-x_0$ est divisible par $10$ donc $n≡x_0\ [10]$.

Propriété

Il en résulte que $n$ est divisible par $10$ si, et seulement si, son chiffre des unités est divisible par $10$, c’est-à-dire s’il se termine par $0$.

Déterminer si un nombre donné est premier

Pour savoir si un nombre est premier, nous pouvons utiliser la contraposée de la proposition « Tout nombre entier $a$ non premier et strictement supérieur à $1$ admet un diviseur strict inférieur ou égal à $\sqrt a$ ».

Propriété

Si $a$ n’admet pas de diviseur premier strict inférieur ou égal à $\sqrt a$, alors $a$ est premier.

Exemple

$\sqrt{367}≈19,2$

Les nombres premiers inférieurs à $\sqrt{367}$ sont $2, 3, 5, 7, 11, 13, 17\text{ et }19$.

• Le nombre $2$ ne divise pas $367$ qui est un nombre impair.
• $3$ ne divise pas $367$ car $3$ ne divise pas la somme de ses chiffres : $3+6+7=16$ et $1+6=7$ non divisible par $3$
• $5$ ne divise pas $367$
• $367=7\times52+3$ donc $7$ ne divise pas $367$
• $367=11\times33+4$ donc $11$ ne divise pas $367$
• $367=13\times28+3$ donc $13$ ne divise pas $367$
• $367=17\times21+10$ donc $17$ ne divise pas $367$
• $367=19\times19+6$ donc $19$ ne divise pas $367$

Il n’existe aucun nombre premier inférieur à $\sqrt{367}$ qui soit un diviseur de $367$ donc $367$ est un nombre premier.

Décomposition en produit de facteurs

Propriété

Un nombre entier naturel strictement supérieur à $1$ est premier ou se décompose de manière unique, à l’ordre près, en produit de nombres premiers.

Démonstration

$n$ est un entier naturel non premier. Il admet alors un diviseur strict premier $p_1$. Donc $n=p_1\times q_1$ où $q_1$ est aussi un diviseur strict de $n$ (sinon $p_1=1$ ou $p_1=n$, ce qui est impossible). Ainsi $q_1$ est strictement inférieur à l’entier $n$.

• Si $q_1$ est premier, alors $n$ est le produit de deux nombres premiers : $n=p_1\times q_1$
• Si $q_1$ n’est pas premier, alors il admet un diviseur strict premier $p_2$. Donc $q_1=p_2\times q_2$ où $p_2$ est un diviseur strict de $q_1$. Ainsi $q_2 < q_1 < n$.
• Si $p_2$ est premier, $n$ est le produit de trois nombres premiers $n=p_1\times p_2\times q_2$

Tant que $q_i$ n’est pas premier, on réitère ce processus. On construit ainsi une suite d’entiers naturels $1 ≤ q_i < q_{i-1} < … < q_3 < q_2 < q_1$.

Comme cette suite est finie, ce processus doit s’arrêter : il existe donc un diviseur $q_k$ premier.

Ainsi, $n$ est le produit de facteurs premiers $n=p_1\times p_2\times …\times p_k\times q_k$.

L’unicité de la décomposition est admise.

Propriété

$n$ est un entier naturel non premier dont la décomposition en produit de facteurs premiers est : $p_1^{α_1}p_2^{α_2}…p_k^{α_k}$

Alors les diviseurs de $n$ sont tous les nombres qui s’écrivent $p_1^{β_1}p_2^{β_2}…p_k^{β_k}$avec $0≤β_1≤α_1$, $0≤β_2≤α_2$, …, $0≤β_k≤α_k$.

Exemple

$n=2\times35\times52$. Ses diviseurs sont tous les nombres $2^∝\times3^β\times5^\gamma$ obtenus en prenant $\alpha$ dans l’ensemble $\lbrace 0\ ;1\rbrace$ , $β$ dans $\lbrace0\ ;1\ ;2\ ;3\rbrace$ et $γ$ dans $\lbrace0\ ;1\ ;2\rbrace$.

Le nombre de diviseurs est le nombre de choix possibles de la liste $\alpha$, $\beta$, $\gamma$. Il y a donc $24$ diviseurs dans l’exemple précédent car $2\times4\times3=24$ (deux choix pour $\alpha$, quatre choix pour $\beta$ et trois choix pour $\gamma$).

D’une manière générale, si la décomposition en produit de facteurs premiers d’un entier naturel $n$ est $n=p_1^{α1}p_2^{α_2}…p_k^{α_k}$, alors le nombre $n$ admet $(α_1+1)(α_2+1)…(α_k+1)$ diviseurs.