Aller au contenu

Arithmétique/Nombres premiers

Leçons de niveau 13
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Nombres premiers
Icône de la faculté
Chapitre no 4
Leçon : Arithmétique
Chap. préc. :Théorèmes de Bézout et Gauss
Chap. suiv. :PPCM

Exercices :

Nombres premiers
fin de la boite de navigation du chapitre
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.


Les dix premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29.

Critère de primalité

[modifier | modifier le wikicode]

Application : tant que , on tente la division de  par

Début de l'exemple
Fin de l'exemple


Lemme d'Euclide

[modifier | modifier le wikicode]

Le lemme suivant est un corollaire immédiat du théorème de Gauss.

Début d'un lemme
Fin du lemme


Décomposition en facteurs premiers

[modifier | modifier le wikicode]
Début d’un théorème
Fin du théorème

(Par convention, est le produit vide.)


Début de l'exemple
Fin de l'exemple


On peut choisir par exemple le plus petit facteur premier dans la décomposition de ou remarquer, plus directement que le plus petit entier strictement supérieur à divisant est premier.

Application au calcul de PGCD

[modifier | modifier le wikicode]

Une alternative à l'algorithme d'Euclide pour calculer le PGCD de deux entiers est, si l'on connait leurs décompositions respectives, de former le produit de tous les nombres premiers intervenant dans ces deux décompositions, élevé chacun à une certaine puissance : l'exposant de dans est le plus petit des deux exposants de dans et dans .

Ensemble des nombres premiers

[modifier | modifier le wikicode]

Infinitude de l'ensemble nombres premiers

[modifier | modifier le wikicode]
Début d’un théorème
Fin du théorème


Théorème des nombres premiers

[modifier | modifier le wikicode]
Début d’un théorème
Fin du théorème


https://oeis.org/A000040 : liste des premiers nombres premiers et leurs propriétés (en anglais)