[PDF] [PDF] Nombres premiers - Laboratoire Analyse, Géométrie et Applications

[PDF] Les nombres premiers

et −p Les deux propositions suivantes vont montrer qu'il existe beaucoup de nombres premiers Proposition 4 1 Tout entier n ≥ 2 admet un diviseur premier

[PDF] Nombres premiers - Labomath

Nombres premiers A- Diviseurs d'un entier naturel 1- Définition Un entier naturel b est un diviseur de l'entier naturel a lorsque le reste de la division

[PDF] La ronde des nombres premiers - Palais de la découverte

Si, au contraire, on ne peut pas décomposer N comme un produit de nombres entiers différents de 1 et N, on dit que N est un nombre premier En fait les nombres 

[PDF] Nombres premiers - Laboratoire Analyse, Géométrie et Applications

— (Euclide) L'ensemble P des nombres premiers est infini 1 Pour ceux qui préf` erent une définition plus imagée, selon Paul Erdös, « un nombre premier est un 

[PDF] Nombres Premiers - Lycée dAdultes

Nombres Premiers Les exercices doivent être effectués suivant leur ordre d' apparition Exercice 1 Comment reconnaître un nombre premier ? 1)Le nombre 97 

[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

PGCD ET NOMBRES PREMIERS I PGCD de deux entiers 1) Définition et propriétés Exemple : Vidéo https://youtu be/sC2iPY27Ym0 Tous les diviseurs de 60 

[PDF] 5e Nombres premiers - Parfenoff org

Nombres premiers I) Définition Un nombre premier est un nombre entier positif qui admet exactement deux diviseurs : 1 et lui-même Remarques : ○ 0 n'est 

[PDF] FEUILLE DEXERCICES Nombres premiers - Maths ac-creteil

Nombres premiers Exercice 1 : 1) Parmi les nombres suivants, trouver le(s) multiple(s) de 14 : 56, 141 et 280 2) Dresser la liste des diviseurs de 28 3) Parmi  

[PDF] Découvrir et utiliser les nombres premiers

Définition a et b désignent des nombres entiers avec b ≠ 0 ○ Effectuer Un nombre premier est un nombre entier qui n'a que deux diviseurs : 1 et lui-même

[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

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