« Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. » Paul ErdösPaul Erdös (1913 – 1996)

Soit p un entier naturel strictement supérieur à 1.On dit que p est un nombre premier si l'ensemble de ses diviseurs dans est {1 ; p}.

Soit a un entier naturel strictement supérieur à 1. a possède au moins un diviseur premier. si a n'est pas premier, alors au moins un des diviseurs premiers de a est inférieur ou égal à a

Pour déterminer si un nombre donné N est premier, on peut cherchers'il est divisible par un nombre premier inférieur ou égal à a

5,31991 Pour savoir si 991 n’est pas premier, il suffit de voir si991 est divisible par un nombre premier inférieur à 32.Exemple :Exemple :

Crible d’Eratosthène.Crible d’Eratosthène.

Ératosthène (en grec ancien Ἐρατοσθένης / Eratosthénês) était un astronome, géographe, philosophe et mathématicien grec

du IIIe siècle av. J.-C. Ératosthène fut nommé à la tête de la bibliothèque d'Alexandrie vers -240 à la demande de Ptolémée III, pharaon d'Égypte,

et fut précepteur de son fils. Astronome passionné, on dit que,

devenu aveugle, il se laissa mourir de faim, ne pouvant plus admirer les étoiles.

On forme une table avec tous les entiers naturels compris entre 2 et N et on raye les uns après les autres, les entiers qui ne sont pas premiers de la manière suivante :

dès que l'on trouve un entier qui n'a pas encore été rayé, il est déclaré premier, et on raye tous les autres multiples de celui-ci.

Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est l'ancêtre du plus récent crible d'Atkin qui est plus rapide mais plus complexe.

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

Crible d’Eratosthène.Crible d’Eratosthène.

Il existe dans une infinité de nombres premiers.

Supposons que l'ensemble des nombres premiers soit un ensemble fini {p1, p2, , pk} .

Soit n = p1 x p2 x x pk + 1.n est strictement supérieur à 1, il admet donc un diviseur premier, c'est-à-dire l'un des nombres pi.pi divise n et pi divise p1 x p2 x x pk , donc pi divise leur différence, c'est-à-dire 1, ce qui est absurde.

L'ensemble des nombres premiers n'est donc pas un ensemble fini.

Tout entier supérieur ou égal à 2 est un nombre premier ouun produit de nombres premiers.

Décomposition d'un nombre en facteurs premiers.Décomposition d'un nombre en facteurs premiers.Décomposition d'un nombre en facteurs premiers.Décomposition d'un nombre en facteurs premiers.

Soit n un entier supérieur ou égal à 2.n peut se décomposer sous la forme :

p11 x p2

2 x …x pk k .

où p1 , p2 , pk sont des nombres premiers tels que p1 < p2 < < pk et 1 , 2 , k des entiers naturels non nuls.

Cette décomposition est appelée décomposition de n en produit de facteurs premiers.

On admet que cette décomposition est unique.

On considère le nombre 360. Il est divisible par 2 et on peut écrire 360 = 2 x 180180 est encore divisible par 2 et on peut écrire 180 = 2 x 9090 est encore divisible par 2 et on peut écrire 90 = 2 x 4545 est divisible par 3 et on peut écrire 45 = 3 x 1515 est divisible par 3 et on peut écrire 15 = 3 x 5Finalement on obtient 360 = 2 x 2 x 2 x 3 x 3 x 5 = 23 x 32 x 5C'est la décomposition du nombre 360 en produit de facteurs premiers.

360 2

180 2

90 2

45 3

15 3

5 5

1

Soit n un entier supérieur ou égal à 2, dont la décomposition en produit de facteurs premiers est :

p11 x p2

2 x …x pk k .

L'ensemble des diviseurs naturels de n est l'ensemble des entiers d s'écrivant sous la forme :

p1 1 x p2

2 x …x pk k .

où 1 , 2 , , k sont des entiers naturels tels que :0 1 1 , 0 2 2 , ... , 0 k k .

On a 360 = 23 x 32 x 5.

Ainsi 22 x 5 = 20 , 23 x 32 = 72 , 2 x 3 x 5 = 30 sont des diviseurs de 360.

232 582 657-1 232 582 657-1

Plus grand nombre premier connu à ce jour(4 septembre 2006)

Plus grand nombre premier connu à ce jour(4 septembre 2006)

Comme ses prédécesseurs, il s'agit d'un nombre de Mersennenombre de Mersenne.Il s'écrit avec 9 808 3589 808 358 chiffres en base 10 !Cela fait environ 1500 feuilles A4 pour écrire ce nombre !

C'est le 10ème nombre de Mersenne premier trouvé par le projet GIMPS et le 44ème nombre de Mersenne premier connu. On l'appelle : M44.

Great Internet Mersenne Prime

Search.

Pour les nombres de Mersenne il existe une méthode (comparativement) très rapide pour déterminer s'ils sont premiers, développée à l'origine par Lucas

en 1878 et améliorée par Lehmer dans les années 1930. On peut effectivement montrer que pour p nombre premier impair

Mp = 2p − 1 est premier si et seulement si Mp divise Sp − 1, où S1 = 4 et pour k > 1, Sk+1 = Sk

2 + 2.