Arithmétique/nombres Premiers

Arithmétique/nombres premiers

Définition

Définition

Un nombre naturel n est premier s'il possède exactement 2 diviseurs naturels distincts, 1 et n.ouUn nombre est premier s'il est divisible uniquement par 1 et par lui-même.

les premiers nombres premiers : $2,3,5,7,11,13,17,19,23,29\,$

Propriété des entiers naturels

Propriété

Tout entier naturel n admet au moins un diviseur premier.

Critère de primalité

Définition

Si un entier naturel n n'est pas divisible par aucun nombre premierdont le carré lui est inférieur ou égal, alors n est premier.

Application : tant que $q < \sqrt{n}\,$ , on tente la division de n par q.

Exemple d'utilisation du critère de primalité

127 premier ? $11 \le \sqrt{127} \le 12$

les nombres premiers inférieurs ou égaux à 11 sont : $2,3,5,7,11\,$

$127 = 2\times 63+1$

$127 = 3\times 42+1$

$127 = 5\times 25+2$

$127 = 7\times 18+1$

$127 = 11\times 11+6$

$\Rightarrow$ 127 est premier

Ensemble des nombres premiers

Théorème

Il existe une infinité de nombres premiers.

Démonstration par l'absurde

On suppose qu'il existe un nombre fini de nombres premiers. Soient $p_1,p_2,p_3,...,p_n\,$ ces nombres premiers.

Soit $N = p_1\times p_2\times...\times p_n +1$ , N n'est pas premier car $\forall j \in \left \{ 1,2,...,n \right \}, N > P_j$ .

Il est donc divisible par l'un des nombres premiers au moins.

Soit j tel que $p_j|N\,$

$\begin{align}\\ N = p_j\times q (q\in\mathbb{N})\\ p_j\times q = p_1\times p_2\times ...\times p_j\times ...\times p_n+1\\ p_j\left ( q-p_1\times p_2\times ...\times p_{j-1}\times p_{j+1}\times ...\times p_n \right ) = 1\\ \Rightarrow p_j|1\end{align}$

or $p_j\,$ est premier : contradiction

$\Rightarrow$ il existe une infinité de nombres premiers.