[PDF] Nombres premiers Il existe cependant quelques rè

View - Download Nombres premiers

Previous PDF

Next PDF

Nombres premiers. Applications

mais il faut que cela reste marginal. Il ne faut pas perdre de vue que le coeur de la le»con doit

µa la maniµere de Ribenboim.

Table des matiµeres

1.2. Familles .. ........................................................ 2

1.3. Quelques formules .. .............................................. 3

2. Aspects algorithmiques .. ................................................ 6

2.2. Factorisation ...................................................... 8

3. Aspects analytiques ...................................................... 12

3.2. La fonction z^eta de Riemann .. .................................. 16

4. Applications diverses .. .................................................. 17

4.2. en cryptographie .. ................................................ 20

4.3. en algµebre .. ...................................................... 20

6. Questions ................................................................ 22

7. Solutions .. .............................................................. 23

Un entierp >1 est dit premier(1)si ses seuls diviseurs sont§1;§p. la forme n=pn11¢¢¢pnrr; oµu lesnisont des entiers naturels non nuls, et oµu lespisont des nombres premiers. Nous noterons alorsPl'ensemble des nombres premiers; la question naturelle est alors de savoir siPest ¯ni ou pas. (Euclide)L'ensemblePdes nombres premiers est in¯ni.

¿un nombre premier est un nombre

qui ne se casse pas quand on le laisse tomber par terre 1 2 i=1peiiavec

0·ei·nde sorte que 2n·(n+ 1)r<2nd'oµu la contradiction.

Remarque :la preuve d'Euclide procµede comme suit : par l'absurde supposons quep1;¢¢¢;pr=

nsont les seuls nombres premiers; soit alorsN=n!+1, (ou bienN= (Q p·np)+1). Comme N > nalorsNn'est pas premier et possµede donc un diviseur premierpqui est donc·nde sorte quepjn! et donc aussiN¡n! = 1 d'oµu la contradiction. Dans la m^eme veine, Kummer propose de raisonner comme suit : on aN:=p1¢¢¢pr>2 etN¡1>1 est alors divisible par un premierpilequel diviseN¡(N¡1) = 1 ce qui est absurde. Remarque :on peut se demander s'il l'ensemble des premiers de la formen!§1 ou (Q

P3q·pq)§

1.2. Familles. |

Nous avons vu que l'ensemblePdes nombres premiers est in¯ni mais il n'est pas si simple d'en exhiber, d'oµu ce paragraphe.

1.2.1|Nombres de Fermat: comme¡1 est racine du polyn^omeX2n+1+ 1 celui-ci est

2 m+ 1 = (22n)k+ 1 = (22n+ 1)((22n)k¡1¡ ¢¢¢+ 1) montre que 2

2n+1 est un diviseur propre de sorte que 2m+1 n'est pas premier. Ainsi si l'on

veut trouver des nombres premiers parmi la famille des 2 m+1, il faut prendremde la forme 2 n. On pose alors pour toutn2N,Fn= 22n+ 1;Fnest len-µeme nombre de Fermat. On tous premiers. Soitppremier divisantF5, on a alors 225´ ¡1 modpde sorte que¹22Z=pZest d'ordre 2 6 p¡1, de k= 10

641 = 1+5:27= 54+24.

Dans le corpsZ=641Z, on a 0 = 641 = 1+5:27soit 27=¡1=5. Ainsi F

5= 232+1 = (27)4:24+1

car 32 = 7:4 + 4. D'oµu dansZ=641Z, on aF5= (¡1=5)4:24+ 1 = (24+ 54)=54= 0. F nest premier. Remarquons cependant que pour n=m+ravecr >0,FnetFmsont premiers entre eux; en e®et on a 2

2n= (22m)2ret dansZ=FmZ, on a alorsFn´(¡1)2r+ 1 modFm.

Ainsi le pgcd de

F P nFnoµuFnest le sous-ensemble de P. de la forme n= 2®p1¢¢¢proµu lespisont des nombres premiers de Fermat. Les constructions n= 2a3bp1¢¢¢proµu les p isont des nombres premiers de la forme 2u3v+ 1.

1.2.2|Nombres de Mersenne: de la factorisationXpq¡1 = (Xp¡1)(Xp(q¡1)+¢¢¢+Xp+1),

2 n¡1 est premier alorsnest un nombre premier. Ainsi pourppremier les 3 nombres M p= 2p¡1 sont dits de MersenneMp= 2p¡1; les premiers exemples sont 3 = 2

2¡1,

7 = 2

3¡1, 31 = 25¡1, 127 = 27¡1 qui sont premiers alors que

2047 = 2

11¡1 = 23£89 ne

qest un diviseur deMpalors l'ordre de la classe de 2 dans pqui doit diviserq¡1 et doncq´1 modp(on a aussiq´1 mod 2p). du fait que pour tout types de nombres premiers sont apparus. premiers ordinaires: ce sont ceux tels que l'anneau des entiersZ[³p] de l'extension cyclo- tomique de nombres, factorielle). Ce sont exactement les p·19 pas de quoi leur donner un nom. seulement si n= 3;4;5;7;8;9;11;12;13;15;16;17;19;20;21;24;25;27;28;32;33;35;36,

40;44;45;48;60;84.

·163 sont 37;59;67;101;103;131;149;157.

les premiers de Sophie Germain: ce sont lesptels que 2p+ 1 est premier. Pour ceux-ci x;y;zne sont faux pour palors 3 les p est un entier; pour p= 5;13,W(p) est premier, on peut se demander si l'ensemble desW(p) premiers qu'il existe une constante

1·k·xtels qu'il existe

naveck2n+ 1 premier, alorsN(x)¸Cx.

1.3. Quelques formules. |

Notons tout d'abord qu'il ne peut pas exister de polyn^omes deZ[X] non constant ne prenant sur Nque des valeurs premiµeres : en e®et soitP(X) = a nXn+¢¢¢+a0de sorte qu'en particuliera02 P. Comme

P(n) tends vers l'in¯ni quandn

tends vers l'in¯ni, il existe une valeurn0µa partir de laquelle jP(n)j> a0. Ainsi pourkassez grand, on ajP(ka0)j> a0alors queP(ka0) est divisible para0. 4 spirales d'Ulam : il s'agit des premiersppour lesquelsn2+n+pest premier pour n= 0;¢¢¢;n¡2 : on remarquera en e®et que pdivise (p¡1)2+ (p¡1) +p, cf. aussi pqui conviennent sont 2;3;5;16 et 41.

On conjecture que pour toutA, il existeBtel que

n

2+n+Bsoit premier pour tout

n= 0;¢¢¢;A. Pour R. Ruby : 103n2¡3945n+ 32381 est premier pourn= 0;1;¢¢¢;42; G. Fung : 47n2¡1701n+ 10181 est premier pourn= 0;1;¢¢¢;42; R. Ruby : 36n2¡810n+ 2753 est premier pourn= 0;1;¢¢¢;44. Un ensembleSest dit diophantien s'il existe un polyn^omePdans

Z[X1;¢¢¢;Xn;Y1;¢¢¢;Ym] tel que (x1;¢¢¢;xn)2Ssi et seulement si il existe des entiers

positifs y

1;¢¢¢;ymtels que

P(x1;¢¢¢;xn;y1;¢¢¢;ym) = 0

si et seulement s'il existe un polyn^ome

Q2Z[X1;¢¢¢;Xm] tel que

S=fQ(x1;¢¢¢;xm)¸1 :x1¸1¢¢¢xm¸1g

En e®et pour

P=Q(X1;¢¢¢;Xm)¡X2Z[X;X1;¢¢¢;Xm] on voit bien qu'un telSest

Q=X(1¡P2).

L'ensemble des nombres premiers est diophantien.

[?] un exemple en (p¡1)!´ ¡1 modp, on montre facilement que la fonction f(n) = 2 + 2(n!) modn+ 1 l'existence d'une constante

Atelle que pour toutn >1,

bA3nc 2 P; A'1;306377883863:::

Pce qui convenons le n'est

pas trµes honn^ete. L'escroquerie est du m^eme genre que la suivante : posons

L= 0;2;003000050000007000000011:::

le bL£10n2c ¡ bL£10(n¡1)2c102n¡1 n-µeme nombre premierpn. 5 t(n) = 2 +nb1 1 + Pm+1 p=2bn+2 p

¡ bn+1

p ccc n+ 2 est un multiple depalors (n+2)=pest un entierqet donc (n+1)=p=q¡1=pet doncbn+2 p

¡bn+1

p µa

1 alors qu'il est nul sipn'est pas un diviseur. Autrement dit la somme compte le nombre de

diviseurs de n+2 compris entre 2 etn+1; ainsi sin+2 est premier on obtientt(n) =n+2 qui est premier alors que sin+ 2 n'est pas premier on a t(n) = 2. Ainsi la formule ne donne que des nombres premiers mais trµes lentement, 2 apparaissant trµes souvent. En utilisant la t(n) = 2 +nb(n+ 1)! + 1 n+ 2¡c(n+ 1)! n+ 2cc laquelle contient moins de symbole et plus de somme, mais requiert de lourds calculs de factoriels.

¼(m) =mX

j=2sin

2³¼

j (j¡1)!2´ sin

2(¼

j )=mX j=2b(j¡1)! + 1 j

¡ b(j¡1)!

j cc

Preuve :Notons tout d'abord que pour

n6= 4 non premier,ndivise (n¡1)! : en e®et sin abavec 2·a6=b·n¡1, alorsabj(n¡1)!. Sinonn=p2pour p >2 premier avec donc

2p·p2¡1 =n¡1 de sorte quendivise 2p:plequel divise (p2¡1)!.

Si b (j¡1)! + 1 j

¡ b(j¡1)!

j cc=bk¡ bk¡1 j cc= 1 alors que si jn'est pas premier, on a (j¡1)! =kjet b (j¡1)! + 1 j

¡ b(j¡1)!

j cc=bk+1 j

¡kc= 0:

Finalement pour

j= 4, on ab3!+1 4

¡ b3!

4 cc= 0. formule p n= 1 +2 nX m=1bbn

1 +¼(m)c1=nc:

p n= 1 +2(bnlnnc+1)X k=1³

1¡ bÃ(k)

n c´ oµu

Ã(k) =k¡1 +Pk

j=2b2 j

1 +Pbp

jc s=1¡bj¡1 s c ¡ bj s c¢´ c. u

0= 3; u1= 0; u2= 2un+1=un¡1+un¡2:

6

2. Aspects algorithmiques

10

11s'avµere ensuite trop lente.

2.1.1|Critµere de Lehmer: il s'agit d'un test e®ectif dans le cas oµu la factorisation de

n¡1 =p®11¢¢¢p®kkest connue. En e®etnest premier si et seulement si pour tout i= 1;¢¢¢;k, il existeai2Ztel que a n¡1i´1 modnetan¡1 p ii^n= 1:

Preuve :Si

a tout p

®iidivisep¡1 et donc

¯nalementp¡1¸n¡1 soitn=p.

est premier si et seulement si 3 (p¡1)=2´ ¡1 modp.

2.1.2|Critµere de Lucas-Lehmer: il s'agit d'un test e®ectif dans le cas oµu la factorisation

dequotesdbs_dbs19.pdfusesText_25

[PDF] college rollinat math

[PDF] diamètre tuyau fonte

[PDF] diametre tube fonte

[PDF] nombre parfait

[PDF] diametre exterieur tuyau fonte

[PDF] canalisation fonte assainissement

[PDF] canalisation fonte eau potable

[PDF] tuyau fonte diametre 100

[PDF] scratch 2

[PDF] fiche technique tuyau fonte pam

[PDF] élaboration de la fonte

[PDF] fabrication de la fonte pdf

[PDF] les fontes pdf

[PDF] pn bride définition

[PDF] en 1092