Arithmétique/Nombres premiers

Définition

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

Critère de primalité

Modèle:Proposition Application : tant que $q<\sqrt{n}$, on tente la division de $n$ par $q$.  Modèle:Exemple

Lemme d'Euclide

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

Décomposition en facteurs premiers

Modèle:Théorème (Par convention, $1$ est le produit vide.) Modèle:Démonstration déroulante

Modèle:Exemple

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

Application au calcul de PGCD

Une alternative à l'algorithme d'Euclide pour calculer le PGCD de deux entiers $a,b\ge 1$ est, si l'on connait leurs décompositions respectives, de former le produit de tous les nombres premiers $p$ intervenant dans ces deux décompositions, élevé chacun à une certaine puissance : l'exposant de $p$ dans $\mathrm{pgcd}(a,b)$ est le plus petit des deux exposants de $p$ dans $a$ et dans $b$.

Lien externe

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