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 imes 63+1$

$127 = 3 imes 42+1$

$127 = 5 imes 25+2$

$127 = 7 imes 18+1$

$127 = 11 imes 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 imes p_2 imes... imes p_n +1$ , N n'est pas premier car $orall j \in \left \{ 1,2,...,n ight \}, 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 imes q (q\in\mathbb{N})\ p_j imes q = p_1 imes p_2 imes ... imes p_j imes ... imes p_n+1\ p_j\left ( q-p_1 imes p_2 imes ... imes p_{j-1} imes p_{j+1} imes ... imes p_n ight ) = 1\ \Rightarrow p_j|1nd{align}$

or $p_j\,$ est premier : contradiction

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

Connexion