Les propriétés des nombres premiers

L'ensemble $\mathbb{P}$ est l'ensemble des nombres premiers :

$$ \mathbb{P} = \Bigl \{2, 3, 5, 7, 11, 13, ...etc. \Bigr\}$$

On appelle nombre premier, un nombre $p \in \mathbb{P}$ qui a uniquement comme diviseur lui-même et $1$.

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

De même, on dira que deux nombres $(a, b) \in \hspace{0.05em} \mathbb{Z}^2$ sont premiers entre eux si leur unique diviseur commun est $1$.

$$ \mathcal{D}(a, b) = \bigl\{1 \bigr\} \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge b = 1 $$

Deux nombres premiers sont premiers entre eux

deux nombres premiers sont premiers entre eux.

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$

Décomposition d'un nombre en facteurs premiers

Tout entier naturel $n \geqslant 2$ se décompose de manière unique en produit facteurs premiers.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

Tout nombre supérieur à 2 possède au moins un diviseur premier

Tout entier naturel $n \geqslant 2$ possède au moins un diviseur premier.

Tout nombre non premier supérieur à 4 possède au moins un diviseur strict

Tout entier naturel $n \geqslant 4 $ non premier possède au moins un diviseur strict $d_0 $ tel que $ d_0 \leqslant \sqrt{n} $.

Lien de primalité entre un nombre premier et tout entier relatif

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

Lemme d'Euclide

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p/a) \enspace ou \enspace (p/b) \qquad \bigl(Lemme \ d'Euclide) $$

Corollaire du lemme d'Euclide

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p=a) \enspace ou \enspace (p=b) \qquad \bigl(Lemme \ d'Euclide \enspace (corollaire)) $$

Démonstrations

Deux nombres premiers sont premiers entre eux

Soient $(p_1, p_2) \in \hspace{0.05em} \mathbb{P} $ deux nombres premiers.

Alors :

$$ \Biggl \{ \begin{align*} \mathcal{D}(p_1) = \bigl\{1, p_1 \bigr\} \\ \mathcal{D}(p_2) = \bigl\{1, p_2 \bigr\} \end{align*} $$

Leur seul diviseur commun est $ 1 $.

Alors,

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$

La réciproque n'est pas vraie.

Par exemple : $16 \wedge 35 = 1$

Et pourtant ces deux nombres ne sont pas premiers.

Décomposition d'un nombre en facteurs premiers

Soit $n \in \mathbb{N}$ un entier naturel avec $n \geqslant 2$.

Ce nombre admet un nombre fini de diviseurs.

si $ n $ est premier

Il n'y a qu'un seul facteur.

$$ n= p_1^{\alpha_1} \enspace \enspace (avec \enspace \alpha_1 = 1) $$

si $ n $ n'est pas premier

On sait que $ n $ a au moins un diviseur premier.

$$ n = n_1 p_1 $$

- Si $ n_1 $ n'est pas premier

On recommence :

$$ n_1 = n_2 p_2 $$

$$ n = p_1. n_2 p_2 $$

- Si $ n_2 $ n'est pas premier

On effectue cette procédure jusqu'au dernier diviseur qui sera nécessairement premier.

On pourra éventuellement retomber sur les mêmes nombres premiers plusieurs fois de suite.

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

Soit finalement,

Tout entier naturel $n \geqslant 2$ se décompose de manière unique en produit facteurs premiers.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

Tout nombre supérieur à 2 possède au moins un diviseur premier

Soit $n \in \mathbb{N}$ un entier naturel avec $n \geqslant 2$.

Deux cas se présentent :

$ n $ est premier

Alors, $ n / n $.

Il a bien au moins un diviseur premier.

$ n $ n'est pas premier

$ n $ possède au moins un diviseur strict.

$$ \mathcal{D}(a) = \bigl\{1, d_1, d_2, \hspace{0.2em} ... \hspace{0.2em}, n \} $$

Soit $ d_1 $ le plus petit diviseur strict de $n $, $d_1 $ est forcément premier, car s'il ne l'était pas, il aurait un diviseur inférieur à lui-même qui diviserait $ n $, et $ d_1 $ ne serait pas le plus petit diviseur de $a $.

Soit finalement,

Tout entier naturel $n \geqslant 2$ possède au moins un diviseur premier.

Tout nombre non premier supérieur à 4 possède au moins un diviseur strict

Soient $n \in \{ \mathbb{N} \hspace{0.2em} \backslash\ \mathbb{P} \} $ un entier naturel non premier avec $n \geqslant 4$, et $d_0 \in \mathbb{N}$ un diviseur strict de $n$.

Alors,

$$ \exists d' \geqslant d_0, \enspace n =d_0 d' $$

En multipliant par $d_0 $ les deux membres,

$$ d_0^2 \leqslant d_0d' \Longleftrightarrow d_0^2 \leqslant n $$

$$ d_0 \leqslant \sqrt{n} $$

Et finalement,

Tout entier naturel $n \geqslant 4 $ non premier possède au moins un diviseur strict $d_0 $ tel que $ d_0 \leqslant \sqrt{n} $.

Lien de primalité entre un nombre premier et tout entier relatif

Soient $ p \in \mathbb{P} $ un nombre premier et $a \in \mathbb{Z} $ un entier relatif.

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

$$ \mathcal{D}(a) = \bigl\{1, \hspace{0.2em} ... \hspace{0.2em}, a \} $$

Si $ p \nmid a $ alors $ p \not\in \mathcal{D}(a) $. D'où le fait que :

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} \mathcal{D}(a) \wedge \mathcal{D}(p) = \bigl\{1 \bigr\} $$

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \wedge p = 1 $$

Réciproque

Si $a \wedge p = 1$, comme $p$ divise uniquement $1$ et lui-même, alors $p \nmid a$.

$$ a \wedge p = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p \nmid a $$

Conclusion

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

Lemme d'Euclide

Soient $ p \in \mathbb{P} $ un nombre premier, $ (a, b) \in \hspace{0.1em} \mathbb{Z}^2 $ deux entiers relatifs.

Si $ p/ab $, alors deux cas se présentent :

$ p $ divise $ a $

Alors, le théorème est vrai

$ p $ ne divise pas $ a $

Alors, le lien de primalité entre un nombre premier et tout entier relatif nous dit que comme $ p \nmid a$, alors $ a \wedge p = 1$.

Or, avec le théorème de Gauss :

$$ \forall (a, b, c) \in (\mathbb{Z})^3,\enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

Ce qui nous permet de dire que $ p $ divise $ b $.

Soit finalement,

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p/a) \enspace ou \enspace (p/b) \qquad \bigl(Lemme \ d'Euclide \bigr) $$

Corollaire du lemme d'Euclide

Soient $ (p, a, b) \in \hspace{0.1em} \mathbb{P}^3 $, trois nombres premiers.

Si $ p/ab $, on a vu plus haut qu'avec le lemme d'Euclide, on a :

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/a \enspace ou \enspace p/b $$

Voyons ce qu'il se passe dans les deux cas.

$ p $ divise $ a $

$ a $ est premier donc ses deux seuls diviseurs sont $ 1 $ et $ a $.

Or, $ p \neq 1 $ par hypothèse car c'est un nombre premier, alors :

$$ p/a \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = a $$

$ p $ divise $ b $

Ce sont les mêmes hypothèses pour $ b $, par conséquent :

$$ p/b \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = b $$

Soit finalement,

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p=a) \enspace ou \enspace (p=b) \qquad \bigl(Lemme \ d'Euclide \enspace (corollaire) \bigr) $$