Nombres premiers

Plan du chapitre "Arithmétique dans ℤ"

Définition et “premières” propriétés

Définition
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}.

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

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

Proposition (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}.
Proposition (existence d'un diviseur premier)
Tout entier naturel {n\ge2} est divisible par au moins un nombre premier.
Proposition
L’ensemble des nombres premiers est infini.

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

Voici une fonction Python qui renvoie la liste des tous les entiers premiers strictement inférieurs à {n^{2}}, où {n} est l’entier passé en argument :

def crible(n) :
return [p for p in range(2, n*n) if p not in
set(j for i in range(2, n) for j in range(i*i, n*n, i))]

On retrouve la liste des entiers premiers strictement inférieurs à {10^{2}} :

>>> crible(10)
[2,3,5,7,11,13,17,19,23,29,31,37,41,
43,47,53,59,61,67,71,73,79,83,89,97]

La fonction crible n’est pas très facile à comprendre au premier abord.
Disons que l’ensemble set(j for i in range(2, n) for j in range(i*i, n*n, i)) est celui de tous les entiers qui sont “entourés” à un moment ou à un autre de la méthode :

>>> set(j for i in range(2, 10) for j in range(i*i, 10*10, i))
{4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,
35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,
63,64,65,66,68,69,70,72,74,75,76,77,78,80,81,82,84,85,86,87,88,
90,91,92,93,94,95,96,98,99}

Sinon, voici une autre solution : la fonction premiers renvoie le tableau des entiers premiers compris entre {2} et {n}. L’intérêt repose dans l’utilisation d’un tableau Numpy de booléens (8 fois moins de taille que des int) et surtout dans le “fancy indexing” qui permet de barrer tous les multiples d’un nombre premier sans créer pour cela une boucle (on utilise une coupe du tableau pour l’affectation : on sait que ça ne nécessite aucune mémoire supplémentaire, car les calculs se font sur place).

def premiers(n):
import numpy as np
a = np.ones(n,’bool’) # n fois 1
a[0] = a[1] = False # on barre 0 et 1
for i in range(2,int(n**0.5)) : # de i=2 à sqrt(n)
if a[i] : a[i*i : n : i] = False # si i non barré, barrer ses suivants
return np.nonzero(a)[0] # renvoyer les entiers premiers

On obtient par exemple (en moins de 50ms) :

>>> premiers(1000)
array([ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997])

Décomposition en produit de facteurs premiers

Dans la suite de ce chapitre, on note {\mathbb{P}} l’ensemble des nombres premiers (notation non standard).

Définition (valuation p-adique d'un entier non nul)
Soit {n} un entier relatif non nul, et soit {p} un entier premier.
Il existe un plus grand entier naturel {k} tel que {p^{k}} divise {n}.
Cet entier est noté {v_{p}(n)} et est appelé valuation {p}-adique de {n}.

Dire que {v_{p}(n)} est nul, c’est dire que {n} n’est pas divisible avec {p} (donc est premier avec {p}).

Dire que {v_{p}(n)} vaut {1}, c’est dire que {n} est divisible par {p}, mais pas par {p^{2}}.

Pour tout {n} de {\mathbb{Z}^{*}}, on a {v_{p}(n)=v_{p}(-n)}, ce qui permet de se limiter à {n>0}.

Proposition (une propriété de la valuation p-adique)
Pour tous entiers non nuls {m} et {n}, et pour tout {p} de {\mathbb{P}}, on a : {v_{p}(mn)=v_{p}(m)+v_{p}(n)}.
Proposition (décomposition en produit de facteurs premiers)
Soit {n} un entier strictement positif.
Alors {n=\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}} où les {\alpha_{p}} sont dans {\mathbb{N}} et tous nuls sauf un nombre fini d’entre eux.
Dans cette écriture, et pour chaque {p} de {\mathbb{P}}, l’entier {\alpha_{p}} est égal à la valuation {p}-adique {v_{p}(n)} de {n}.
Une telle écriture de {n} est donc unique (à l’ordre près des facteurs).
On l’appelle décomposition de {n} en produits de facteurs premiers.

Si {n=\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}}, alors on peut dire que {-n=-\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}} est la factorisation de {-n} (peu utilisé en fait).

Le produit {\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}} a un sens parce qu’il contient un nombre fini de facteurs distincts de {1}.

Dans cette écriture de {n}, les entiers {p} pour lesquels {\alpha_{p}\ge1} sont les diviseurs premiers de {n}.

Pour l’entier {n=1}, tous les exposants {\alpha_{p}} sont nuls.

Pour prendre un exemple, la décomposition de {n=4200} est {n=2^{3}\cdot 3\cdot 5^{2}\cdot 7}.

Proposition (caractérisation de la divisibilité en termes de valuations p-adiques)
Soit {n} et {m} deux entiers strictement positifs.
Soit {n=\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}} et {m=\displaystyle\prod_{p\in\mathbb{P}}p^{\beta_{p}}} leurs décompositions en produits de facteurs premiers.
Alors {m} divise {n} si et seulement si {\beta_{p}\le \alpha_{p}} pour tout {p} de {\mathbb{P}}.
Autrement dit : {m\mid n \Leftrightarrow (\,\forall\, p\in\mathbb{P},\;v_{p}(m)\le v_{p}(n)\,)}.

Une conséquence est que le nombre de diviseurs distincts positifs de {n} est {\displaystyle\prod_{p\in\mathbb{P}}(\alpha_{p}+1)}.

Par exemple l’entier {4200=2^{3}\cdot 3\cdot 5^{2}\cdot 7}possède {4\cdot 2\cdot 3\cdot 2=48} diviseurs distincts dans {\mathbb{N}}.
D’ailleurs les voici (on utilise la fonction diviseurs vue précédemment :

>>> diviseurs(4200)
[1,2,3,4,5,6,7,8,10,12,14,15,20,21,24,25,28,30,35,40,42,50,
56,60,70,75,84,100,105,120,140,150,168,175,200,210,280,300,350,
420,525,600,700,840,1050,1400,2100,4200]
>>> len(_)
48

Proposition (expression du pgcd et du ppcm à l'aide des valuations p-adiques)
Soit {n} et {m} deux entiers strictement positifs.
Soit {n=\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_{p}}} et {m=\displaystyle\prod_{p\in\mathbb{P}}p^{\beta_{p}}} leurs décompositions en produits de facteurs premiers.
Alors {m\wedge n=\displaystyle\prod_{p\in\mathbb{P}}p^{\gamma_{p}}\;}et {\;m\vee n=\displaystyle\prod_{p\in\mathbb{P}}p^{\delta_{p}}}, avec {\begin{cases}\gamma_{p}=\min(\alpha_{p},\beta_{p})\cr \delta_{p}=\max(\alpha_{p},\beta_{p})\end{cases}} pour tout {p} de {\mathbb{P}}.

On retrouve aisni {(m\wedge n)(m\vee n)=mn}. En effet, {\gamma_p+\delta_p=\alpha_p+\beta_p} pour tout {p} de {\mathbb{P}}.

Un peu de programmation Python

La fonction factor forme la liste (ordonnée suivant les valeurs croissantes) de tous les diviseurs premiers {p} de {n} (avec répétitions éventuelles, selon la valuation de {p} dans {n}) :

def factor(n):
fp = [] # la liste des facteurs premiers de n, vide au départ
pfp = 1 # le produit des éléments de cette liste, 1 au départ
x = n # fait une copie de l’entier n qu’on veut factoriser
d = 2 # le plus petit diviseur potentiel de n
while pfp != n : # tant qu’on n’a pas complètement factorisé n
while x % d == 0 : # tant que d est un diviseur de x
fp.append(d) # on ajoute le diviseur (premier) d à la liste fp
pfp *= d # on actualise le produit des facteurs premiers
x //= d # on actualise l’entier x restant à factoriser
d += 1 # on passe au diviseur potentiel suivant
return fp # renvoie la factorisation

Voici la factorisation de l’entier {1037400} :

>>> factor(1037400)
[2, 2, 2, 3, 5, 5, 7, 13, 19]

On écrit maintenant une deuxième fonction de factorisation. C’est juste une variation sur l’idée précédente. Mais on utilise un dictionnaire plutôt qu’une liste : dans ce dictionnaires les clefs sont les diviseurs premiers de {n}, et les valeurs associées à ces clefs sont les valuations {p}-adiques correspondantes. La toute dernière instruction sert à renvoyer un résultat sous forme d’une liste de couples {(p,v_{p}(n))}, triée suivant les valeurs croissantes de {p}.

def factor2(n) :           # donne la liste des couples (p,vp(n))
vp = {} # le dictionnaire des valuations p-adiques
pf = 1 # le produit des facteurs déjà obtenus
x = n # fait une copie de l’entier n qu’on veut factoriser
d = 2 # le plus petit diviseur potentiel de n
while pf != n : # tant qu’on n’a pas complètement factorisé n
while x % d == 0 : # tant que d est un diviseur de x
if d in vp : # si le facteur premier d avait déjà été rencontré
vp[d] += 1 # on augmente la valuation d’une unité
else : vp[d] = 1 # sinon on pose une valuation égale à 1
pf *= d # on actualise le produit des facteurs
x //= d # on actualise l’entier x restant à factoriser
d += 1 # on passe au diviseur potentiel suivant
return [(p,vp[p]) for p in sorted(vp)] # liste triée des (p,vp(n))

Voici à nouveau la factorisation de l’entier {1037400} :

>>> factor2(1037400)
[(2, 3), (3, 1), (5, 2), (7, 1), (13, 1), (19, 1)]

Voici maintenant une fonction (très compacte) renvoyant le {n}-ème nombre premier :

def nthprime(n):
c = 1 # un compteur de nombres premiers
p = 1 # initialise le futur n-ième nombre premier
while c < n : # tant qu’on n’a pas atteint n nombres premiers
p += 2 # on passe au candidat suivant
j = 3 # diviseur potentiel de p
ok = True # initialise condition de primalité
while ok and j*j <= p : # tant qu’on ne dépasse pas sqrt(p)
ok = p%j # on continue si j ne divise pas p
j += 2 # et on passe au diviseur potentiel suivant
if ok : c += 1 # si on est sorti avec ok=True, p était premier
return max(p, 2) # max utile uniquement si n=1 donc si p=1

On obtient le {10000}-ième nombre premier en une demi-seconde environ.

>>> nthprime(10000)
104729

Enfin, la fonction suivante renvoie la liste ordonnées de {n} plus petits entiers premiers :

def nprimes(N):
primes = [2] # initialise la liste des nombres premiers
def primable(k) :
for j in primes : # pour chaque nombre premier de la liste
if k % j == 0 : # si j divise k
return 0 # alors k n’est pas premier!
if j*j > k : # si on dépasse sqrt(k)
return 1 # alors k est “primable”
n = 1 # initialise le compteur de nombres premiers
k = 3 # 3 est le plus petit entier premier impair
while n < N : # tant qu’on n’a pas obtenu N nombres premiers
if primable(k) : # si k est “primable” (donc premier!)
n += 1 # alors on incrémente le compteur n
primes.append(k) # et on ajoute k à la liste “primes”
k += 2 # on passe à l’entier impair suivant
return primes # renvoie la liste des n plus petits premiers

Voici par exmple la liste des {100} plus petits nombres premiers :

>>> nprimes(100)
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,
83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,
173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,
263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,
359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541]

Page précédente : entiers premiers entre eux
Page suivante : congruences