Arithmétique des entiers (4/4)

Soit {p} un entier naturel.
On dit que {p} est premier si {p\ge2} et si ses seuls diviseurs dans {\mathbb{N}} sont {1} et {p}.

• 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…

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.

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}.

Tout entier naturel {n\ge2} est divisible par au moins un nombre premier.

L’ensemble des nombres premiers est infini.

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}}

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]}.