Arithmétique/Nombres premiers

Une page de Wikiversité.

**Nombres premiers**
Leçon : Arithmétique

Chapitre 3
Chap. préc. :	PGCD
Chap. suiv. :	Théorèmes de Bézout et Gauss

En raison de limitations techniques, la typographie souhaitable du titre, « Arithmétique : Nombres premiers
Arithmétique/Nombres premiers », n'a pu être restituée correctement ci-dessus.

[modifier] Définition

Définition

Un nombre naturel n est premier s'il possède exactement 2 diviseurs naturels distincts, 1 et n.
ou
Un 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

[modifier] Propriété des entiers naturels

Propriété

Tout entier naturel n plus grand que 1 admet au moins un diviseur premier.

[modifier] Critère de primalité

Définition

Si un entier naturel n n'est pas divisible par aucun nombre premier dont 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

[modifier] 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.

Arithmétique

PGCD

Théorèmes de Bézout et Gauss

Arithmétique/Nombres premiers

Une page de Wikiversité.

Sommaire

[modifier] Définition

[modifier] Propriété des entiers naturels

[modifier] Critère de primalité

[modifier] Ensemble des nombres premiers

Affichages

Outils personnels

Rechercher

Navigation

Contribuer

Imprimer / exporter

Boîte à outils