Arithmétique des entiers (4/4)

⇧ 1 2 3 ④

Entiers premiers

D. Entiers premiers

Soit

{p}

un entier naturel.
On dit que

{p}

est premier si

{p\ge2}

et si ses seuls diviseurs dans

{\mathbb{N}}

sont

{1}

{p}

R. Remarques

On remarque que ${1}$ n'est pas considéré comme un nombre premier.
On peut aussi adopter la définition suivante : un entier naturel ${p}$ est dit premier s'il possède exactement deux diviseurs distincts dans ${\mathbb{N}}$ (ce qui exclut les entiers ${0}$ et ${1}$ )
Les dix plus petits nombres premiers sont ${2,3,5,7,11,13,17,19,23,29}$ .
À l'exception de ${2}$ , tous les nombres premiers sont impairs.
Dans la phrase " ${a}$ est premier avec ${b}$ ", il n'y a souvent pas de nombre premier...

P. Si p est premier et ne divise pas a

Soit

{p}

un nombre premier, et

{a}

un entier relatif.
Si

{p}

ne divise pas

{a}

, alors

{p}

est premier avec

{a}

.
En particulier, un entier premier

{p}

est premier avec tous les entiers de

{\{1,\ldots,p-1\}}

.
Une autre conséquence est que deux nombres premiers distincts sont premiers entre eux.

P. Entier premier divisant un produit

Soit

{p}

un nombre premier, et soit

{a_1,a_2,\ldots,a_n}

une famille d'entiers relatifs.
Si

{p}

divise le produit

{a_1a_2\ldots a_n}

, alors

{p}

divise l'un au moins des entiers

{a_k}

P. Existence d'un diviseur premier

Tout entier naturel

{n\ge2}

est divisible par au moins un nombre premier.

P. L'ensemble des nombres premiers

L'ensemble des nombres premiers est infini.

R. Crible d'Erathosthène

Crible d'Erathosthène constitue une méthode artisanale bien connue de recherche de nombres premiers.

Ici on se restreint à ${[[1,100]]}$ (on a disposé ces entiers dans une grille ${10\times 10}$ .

On entoure l'entier ${1}$ , qui n'est pas premier :

${\begin{array}{rrrrrrrrrr}\boxed{1}&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\51&52&53&54&55&56&57&58&59&60\\61&62&63&64&65&66&67&68&69&70\\71&72&73&74&75&76&77&78&79&80\\81&82&83&84&85&86&87&88&89&90\\91&92&93&94&95&96&97&98&99&100\end{array}}$

Ensuite on entoure les entiers pairs (sauf ${2}$ lui-même) :

${\begin{array}{rrrrrrrrrr}\boxed{1}&2&3&\boxed{4}&5&\boxed{6}&7&\boxed{8}&9&\boxed{10}\\11&\boxed{12}&13&\boxed{14}&15&\boxed{16}&17&\boxed{18}&19&\boxed{20}\\21&\boxed{22}&23&\boxed{24}&25&\boxed{26}&27&\boxed{28}&29&\boxed{30}\\31&\boxed{32}&33&\boxed{34}&35&\boxed{36}&37&\boxed{38}&39&\boxed{40}\\41&\boxed{42}&43&\boxed{44}&45&\boxed{46}&47&\boxed{48}&49&\boxed{50}\\51&\boxed{52}&53&\boxed{54}&55&\boxed{56}&57&\boxed{58}&59&\boxed{60}\\61&\boxed{62}&63&\boxed{64}&65&\boxed{66}&67&\boxed{68}&69&\boxed{70}\\71&\boxed{72}&73&\boxed{74}&75&\boxed{76}&77&\boxed{78}&79&\boxed{80}\\81&\boxed{82}&83&\boxed{84}&85&\boxed{86}&87&\boxed{88}&89&\boxed{90}\\91&\boxed{92}&93&\boxed{94}&95&\boxed{96}&97&\boxed{98}&99&\boxed{100}\end{array}}$

Puis on entoure les multiples de ${3}$ qui ne sont pas déjà entourés (ce sont donc les multiples impairs de ${3}$ ), sauf ${3}$ lui-même :

${\begin{array}{rrrrrrrrrr}\boxed{1}&2&3&\boxed{4}&5&\boxed{6}&7&\boxed{8}&\boxed{9}&\boxed{10}\\11&\boxed{12}&13&\boxed{14}&\boxed{15}&\boxed{16}&17&\boxed{18}&19&\boxed{20}\\\boxed{21}&\boxed{22}&23&\boxed{24}&25&\boxed{26}&\boxed{27}&\boxed{28}&29&\boxed{30}\\31&\boxed{32}&\boxed{33}&\boxed{34}&35&\boxed{36}&37&\boxed{38}&\boxed{39}&\boxed{40}\\41&\boxed{42}&43&\boxed{44}&\boxed{45}&\boxed{46}&47&\boxed{48}&49&\boxed{50}\\\boxed{51}&\boxed{52}&53&\boxed{54}&55&\boxed{56}&\boxed{57}&\boxed{58}&59&\boxed{60}\\61&\boxed{62}&\boxed{63}&\boxed{64}&65&\boxed{66}&67&\boxed{68}&\boxed{69}&\boxed{70}\\71&\boxed{72}&73&\boxed{74}&\boxed{75}&\boxed{76}&77&\boxed{78}&79&\boxed{80}\\\boxed{81}&\boxed{82}&83&\boxed{84}&85&\boxed{86}&\boxed{87}&\boxed{88}&89&\boxed{90}\\91&\boxed{92}&\boxed{93}&\boxed{94}&95&\boxed{96}&97&\boxed{98}&\boxed{99}&\boxed{100}\end{array}}$

Ensuite on entoure les multiples non déjà entourés de ${5}$ :

${\begin{array}{rrrrrrrrrr}\boxed{1}&2&3&\boxed{4}&5&\boxed{6}&7&\boxed{8}&\boxed{9}&\boxed{10}\\11&\boxed{12}&13&\boxed{14}&\boxed{15}&\boxed{16}&17&\boxed{18}&19&\boxed{20}\\\boxed{21}&\boxed{22}&23&\boxed{24}&\boxed{25}&\boxed{26}&\boxed{27}&\boxed{28}&29&\boxed{30}\\31&\boxed{32}&\boxed{33}&\boxed{34}&\boxed{35}&\boxed{36}&37&\boxed{38}&\boxed{39}&\boxed{40}\\41&\boxed{42}&43&\boxed{44}&\boxed{45}&\boxed{46}&47&\boxed{48}&49&\boxed{50}\\\boxed{51}&\boxed{52}&53&\boxed{54}&\boxed{55}&\boxed{56}&\boxed{57}&\boxed{58}&59&\boxed{60}\\61&\boxed{62}&\boxed{63}&\boxed{64}&\boxed{65}&\boxed{66}&67&\boxed{68}&\boxed{69}&\boxed{70}\\71&\boxed{72}&73&\boxed{74}&\boxed{75}&\boxed{76}&77&\boxed{78}&79&\boxed{80}\\\boxed{81}&\boxed{82}&83&\boxed{84}&\boxed{85}&\boxed{86}&\boxed{87}&\boxed{88}&89&\boxed{90}\\91&\boxed{92}&\boxed{93}&\boxed{94}&\boxed{95}&\boxed{96}&97&\boxed{98}&\boxed{99}&\boxed{100}\end{array}}$

On continue en entourant les multiples non déjà entourés de ${7}$ .
L'entier premier ${11}$ vérifie ${11^{2}>100}$ donc c'est fini.
À ce stade, les entiers non entourés sont les entiers premiers de ${[1,100]}$ :

${\begin{array}{rrrrrrrrrr}\boxed{1}&2&3&\boxed{4}&5&\boxed{6}&7&\boxed{8}&\boxed{9}&\boxed{10}\\11&\boxed{12}&13&\boxed{14}&\boxed{15}&\boxed{16}&17&\boxed{18}&19&\boxed{20}\\\boxed{21}&\boxed{22}&23&\boxed{24}&\boxed{25}&\boxed{26}&\boxed{27}&\boxed{28}&29&\boxed{30}\\31&\boxed{32}&\boxed{33}&\boxed{34}&\boxed{35}&\boxed{36}&37&\boxed{38}&\boxed{39}&\boxed{40}\\41&\boxed{42}&43&\boxed{44}&\boxed{45}&\boxed{46}&47&\boxed{48}&\boxed{49}&\boxed{50}\\\boxed{51}&\boxed{52}&53&\boxed{54}&\boxed{55}&\boxed{56}&\boxed{57}&\boxed{58}&59&\boxed{60}\\61&\boxed{62}&\boxed{63}&\boxed{64}&\boxed{65}&\boxed{66}&67&\boxed{68}&\boxed{69}&\boxed{70}\\71&\boxed{72}&73&\boxed{74}&\boxed{75}&\boxed{76}&\boxed{77}&\boxed{78}&79&\boxed{80}\\\boxed{81}&\boxed{82}&83&\boxed{84}&\boxed{85}&\boxed{86}&\boxed{87}&\boxed{88}&89&\boxed{90}\\\boxed{91}&\boxed{92}&\boxed{93}&\boxed{94}&\boxed{95}&\boxed{96}&97&\boxed{98}&\boxed{99}&\boxed{100}\end{array}}$

P. Petit théorème de Fermat

Soit

{p}

un entier premier.
Pour tout entier relatif

{a}

, on a :

{a^{p}\equiv a~[p]}

.
En particulier, si

{a}

n'est pas divisible par

{p}

, on a :

{a^{p-1}\equiv 1~[p]}

Décomposition en facteurs premiers

Ce contenu nécessite une souscription active

E. Exercices conseillés

⇧ 1 2 3 ④