[PDF] [PDF] Nombres premiers ( )n ( )1 - Thierry Sageaux

Hérédité : On suppose que

()1kH+ est vraie. Si k+1 est premier, rien à dire. Sinon, alors k+1 est divisible par 1, k+1 et au

2l construit une suite strictement décroissante

2 31 ... ... 1ik l l l l+ > > > > > > > d"entiers

strictement plus grand que 1. Donc la suite est finie, ce qui signifie que l"un d"eux est premier.

La propriété est initialisée au rang 2, elle est héréditaire, donc elle est vraie pour tout

entier n>1.  Théorème de décomposition en facteurs premiers (2.C) : Soit n un entier naturel

2n³. Le nombre n se décompose en produit de facteurs premiers (unique à l"ordre près des

facteurs). On a donc 1 i l i in pa ==Õ avec 1i ip p+> pour tout entier i et iaÎ?. 2 Démonstration : Existence : Si n est premier, c"est fini. Si n n"est pas premier, par (2.B), il existe

1q qui divise n et on a 1 1n q n= avec 11n n< <. On itère et on a une suite strictement

décroissante d"entiers naturels

1 2... ...in n n n> > > > > donc, elle est finie. Ainsi, il existe

kÎ? tel que 1k kn q+= soit premier et 1 1k i in q =Õ, soit en regroupant les termes, 1 i l i in pa Unicité : Propriété difficile qui nécessite l"unicité du quotient (autrement dit que ? est factoriel) Décomposer 11400 [=2^3*3*5^2*19], Idem avec 17523. Que peut-on dire des nombre qui ont exactement trois diviseurs ? [Ce sont des carrés parfaits]

Le problème de Freudenthal

Sur le même type : Le facteur et les trois filles. " Un homme bavarde avec le facteur sur la pas de la porte de sa maison. -" C"est amusant, je viens de remarquer que la somme des âges des mes trois filles est égal au numéro de ma maison dans la rue. Je suis sûr que si je vous apprends que le produit de leurs âges est 36, vous saurez me dire leurs âges respectifs ! » Le facteur réfléchit un moment et lui répond ; -" Je suis désolé, mais je ne peux pas trouver. »

L"homme s"exclame alors :

-" Ah oui ! J"avais oublié de vous dire que l"aînée est blonde ! » Quelques secondes après, le facteur lui donne la bonne réponse !.

Corollaire (2.D) : Soit

1 i l i in pa ==Õ une décomposition en facteurs premiers. Si d|n, alors d s"écrit 1 i l i id pb ==Õ avec 0i ib a£ £.

Démonstration : Ü

1 i i k i inpda b- == ÎÕ? car 0i ia b- ³.

? On peut la démontrer en utilisant l"unicité de la décomposition. Si d|n, alors il existe q

tel que n=dq. D"après la décomposition en facteurs premiers, on peut écrire 1 i l i id pb ==Õ et 1 i l i iq pg ==Õ, donc 1 i i l i i n pg b+ ==Õ, mais la décomposition étant unique, i i ig b a+ =.  Rechercher les diviseurs simultanés de 539 et 147. Quels sont les diviseurs de 60 ? Ce grand nombre de diviseurs a fait que 60 a été choisi pour la base des angles, donc de l"heure. C"est la base sexagésimale. Il se trouve aussi que 60 est divisible par 4 (saisons), 12 (mois), 30 (lunaisons).

II Recherche de nombres premiers.

3

1. Les cribles.

9 15

21 27 ...

15 25 35 45 ...

21 35 49 63 ...

27 45 ... ... ...

33 55 ... ... ...

Eratosthène est le crible le plus connu, mais il y a mieux : Le crible de Sundaram : On commence par un 9 en haut à gauche du tableau, puis on remplit colonne après colonne ou ligne après ligne avec des suites arithmétiques de raisons successives 6, 10,

14, 18, ...

Proposition (2.E) : Un nombre impair plus grand que 3 est premier si et seulement si il n"est pas dans la grille..

Démonstration :

On note ,k ju le nombre de la ligne k et de la colonne j, avec k et j entiers naturels. La ligne kL commence par le terme ,09 6ku k= + et la raison de la suite est 6+4k.

Ainsi,

,(9 6 ) (6 4 ) (2 3)(2 3)k ju k k j k j= + + + = + +.

CN : Par contraposée,

,k ju n"est pas premier compte tenu de la factorisation précédente. CS : Toujours par contraposée, si 2n+1 n"est pas premier, alors

2 1n pq+ = avec p et q

impairs plus grands que 2. Donc il existe k et l tels que

2 3p k= + et 2 3q l= +, donc n est

dans le tableau.

2. Test de primalité :

Proposition (2.F) :

Si n n"est pas premier, alors il admet au moins un diviseur premier p tel que p n£.

Démonstration :

Avec le lemme 2.B, si n n"est pas premier, il existe p premier qui divise n.

Parmi tous ces nombres p, on note

0p le plus petit. On a alors 2

0 0n p q p= ³ car, par

définition,

0q p³. D"où 0p n£. 

Montrer que 7

7M 2 1 127= - = est premier. [On utilise la contraposée de la proposition]

3. Des machines à donner des premiers :

Les chercheurs ont toujours cherché des fonctions ou des suites de nombres qui

donnent de très grands nombres premiers. Mais sans succès jusqu"à présent. Tous les grands

mathématiciens s"y sont cassés les dents. Il n"existe toujours pas de 'formule" génératrice de

premiers.

On a le

polynôme de Legendre 2( ) 2 29f n n= + est premier pour n variant de 0 à 28. Montrer que f(n) est composé pour une infinité de valeurs de n. Montrer que 31 divise f(n) pour une infinité de valeurs de n. Le polynôme d"Euler : 2( ) 41f n n n= - + qui est premier pour n variant de -39 à 40 (et dans presque la moitié des valeurs entre 0 et 10 millions). Le polynôme de Ruby : 2( ) 103 3945 34 381f n n n= - + La spirale d"Ulam1 est obtenue en écrivant les entiers en tournant et en noircissant les nombres premiers. On voit apparaître des diagonales.... Etonnant ! p41.

1 Stanislaw Marcin Ulam (1909-1984) physicien polonais naturalisé américain en 1943, il est connu pour avoir

résolu le problème d"amorce de la fusion de la bombe H ainsi que la méthode de Monté Carlo permettant de

donner un résultat à des problèmes statistiques via le hasard. Il apprit les mathématiques à l"age de 14 ans,

4 Actuellement, on peut trouver si un nombre est premier en

6(log( ))n opérations, c"est

l"algorithme AKS (pour Agrawal, Kayal et Saxena)

III Jouons avec les nombres premiers.

1. L"indicatrice d"Euler :

Définition :

Si n est un entier naturel non nul, on note ( )nj le nombre d"entiers naturels p avec 1p n£ < premiers avec n. Proposition (2.G) : Si n est un entier naturel non nul, dont une décomposition en facteurs premiers est 1 i k i in pa ==Õ alors 1

1( ) ( 1)i

k i i i n p paj-

Démonstration :

· Si n est premier, alors il est évident que ( ) 1n nj= -.

· Si

n pa=, montrons de 1( ) ( 1)n p paj-= - : il suffit de compter ceux qui ne sont pas premiers avec n. Il y a tous les multiples de p : p, 2p, 3p ...

1( 1)p p p pa a-- = -. Il y en a

donc

11pa-- que l"on retranche aux 1pa- nombres entiers qui sont dans [[1,n. Soit

1 1( ) 1 ( 1) ( 1)n p p p p p pa a a a aj- -= - - - = - = -

· Il reste à montrer que si

n p qa b= est le produit de deux nombres premiers distincts, alors ( ) ( ). ( )n p qa bj j j=(on dit que j est sous-multiplicative). Il suffit de bien compter :

Le nombre d"entiers de

[[1,n multiples de p : il y en a 11q pb a--. Pour le voir, on regarde la liste des multiples de p et surtout le dernier avant n :

s"étant rendu compte qu"il en avait besoin pour comprendre la théorie de relativité d"Einstein. Il aurait découvert

sa spirale lors d"une conférence dans laquelle il s"ennuyait. 5 1( 1) , 2 , 3 , ... , , np p q p p p p q p p q a b a b a b

Le nombre d"entiers de

[[1,n multiples de q : il y en a 11p qa b--.

Le nombre d"entiers de

[[1,n multiples de pq : il y en a 1 11p qa b- --. Ici, il faut voir que si p et q sont premiers entre eux, la seule façon d"obtenir un nombre divisible par p et q est d"avoir un multiple de pq. (C"est le lemme de Gauss de la leçon 3)

Donc au total, nous avons

1 1 1 1 1 1 1 1

1 1 1 1 ( 1) ( 1) ( 1) ( 1) ( 1) ( 1)( 1)p q p q q p p q p q p q q p p q p q pq p q p q p q a b a b b a a b a b a b b a a b a b a b- - - - - - - -

On finit la preuve par induction.

quotesdbs_dbs41.pdfusesText_41