[PDF] TEST DE PRIMALITÉ DE LUCAS, NOMBRES DE

Démonstrations de primalité Nombres de Mersenne et de Fermat

Démonstrations de primalité Nombres de Mersenne et de Fermat 1 Introduction Le tableau suivant montre l'évolution du record du plus grand nombre premier connu, aanvt l'avénement de l'ordinateur : 1588 217 1 = 131071 6 chi res Cataldi 1588 219 1 = 524287 6 chi res Cataldi 1772 231 1 10 chi res Euler 1867 259 1 =179951 13 chi res Landry

TEST DE PRIMALITÉ DE LUCAS, NOMBRES DE

est un nombre premier, est appelé nombre de Mersenne Pour donner un exemple déjà ancien, Euler a démontré que M 31 est pre-mier en utilisant le théorème suivant Théorème 4 1 Soient pet qdeux nombres premiers imairs p Si pdivise M q, alors p 1 mod qet p 1 mod 8 Mais revenons aux suites de Lucas Soit (V n) dé nie par récurrence

Logique et calcul : Les chasseurs de nombres premiers

Grâ ce à ce test, le plus grand nombre premier connu est un nombre de Mersenne Il s'agit de 23021377 –1 (dé couvert en 1998 par Clarkson, Woltman et Kurowki), qui comporte 909 526 chiffres On espè re trouver un nombre premier de un million de chiffres avant l'an 2000 On connaît aujourd'hui 37 nombres premiers de Mersenne, qui sont

Nombres premiers, divisibilité

1 Les nombres de Mersenne On appelle n-ième nombre de Mersenne , le nombre M n = 2n 1 On remarque qu'une condition nécessaire pour que M n soit un nombre premier est que n soit lui-même premier Chercher ce qui concerne les nombres de Mersenne dans l'aide en ligne Ecrire un programme en Maple qui prend en entrée l'entier N et calcule la

Robert CONTIGNON Paulo PORTINHA

Dé nition 2 4 Un nombre de Mersenne est un terme de la suite (M n) n2N = 2 n 1 Un nombre premier de Mersenne est un nombre 2p 1 où pest premier On le note M p À présent, on peut énoncer le principe du test de Lucas-Lehmer : Théorème 2 3 (Théorème/Test de Lucas-Lehmer) Soit la suite d'entiers (s i) i 0 dé nie arp currérence de la

110: nombres premiers Applications - Centre de Recherche en

2 3 Nombres de Mersenne [2] Théorème 11 Pour qu'un nombre de la forme an 1 soit premier, il est néecssaire que a= 2 et nest un nombre premier Dé nition 5 Des nombres de la forme 2p 1 sont appelés nombres de Mersenne noté M p Réciproque fausse Exemple 4 211 1 = 23 89: On aime bien utiliser les nombres de Mersenne pour trouver des

Les nombres premiers

Il n’existe pas de machine à générer des nombres pre-miers Par contre, on dispose de résultats concernant la densité des nombres premiers (hors programme) Le plus grand nombre premier connu à ce jour (2016) est le nombre de Mersenne suivant : 274 207 281 −1 qui comporte 22 338 618 chiffres Test de primalité ou critère d’arrêt

Mathématiques discrètes L1 Informatique I23 Exercice 4

3 Les nombres de la forme Mp = 2 p 1 avec p premier sont appelés nombres de Mersenne Montrer que M7 est premier 4 On dit qu'un nombre (entier) est parfait s'il est égal à la somme de ses diviseurs autres que lui-même Par exemple, 6 est un nombre parfait car ses diviseurs di érents de 6 sont 1, 2 et 3 et on a 6 = 1+2+3

Publications mathématiques de Besançon - Centre Mersenne

Avant d'énoncer le théorème, il est utile de rappeler un certain nombre de dé nitions On note g l'idéal de dé nition (premier, homogène) de l'adhérence de Zariski G de G dans P n et : A := k [X 0;:::;X n]=g: On dira qu'une sous-variété V de G est dé nie dans G par un premier p de A si V = G \ Z (p)

Approximations diophantiennes des nombres - Centre Mersenne

En l honneur de Michel Mendès Franche RÉSUMÉ Nous établissons pour tout nombre sturmien (de dé-veloppement dyadique sturmien) des propriétés d approximation diophantienne très précises, ne dépendant que de l angle de la suite sturmienne, généralisant ainsi des travaux antérieurs de Ferenczi-Mauduit et Bullett-Sentenac

[PDF] a^n-1 premier alors a=2

[PDF] le tourisme des français en 2016

[PDF] français vacances statistiques 2016

[PDF] tourisme français ? l'étranger

[PDF] ou partent les français en vacances

[PDF] pourcentage de français qui partent en vacances ? l'étranger

[PDF] nombre marche tour eiffel 2 etage

[PDF] hauteur tour eiffel 1er etage

[PDF] 1 etage combien de marches

[PDF] combien de marches pour monter au deuxième étage de la tour eiffel

[PDF] fonction logarithme bac pro exercice

[PDF] nombre de molécules dans 1 litre d'air

[PDF] exercices fonctions logarithmes et exponentielles

[PDF] nombre d'atomes sur terre

[PDF] pv=nrt

Le test de Lucas

Daniel PERRIN

1

Enonce

Voici le theoreme de Lucas-Lehmer (voir [3] et [1]) :

1.1 Theoreme.Soitpun nombre premier impair etMp(ouM) le nombre

de Mersenne2p1. On considere la suiteLndenie par recurrence par L

0= 4etLn+1=L2n2. AlorsMest premier si et seulement siLp2est

multiple deM.

1.2 Commentaire.Ce test est d'une ecacite extraordinaire pour determiner

si un nombre de Mersenne est premier ou non. Il est tres facile d'ecrire un programme dans ce but. En voici un surxcas:

Lucas(p):=f

local n,M, u; u:=4;

M:=2^p-1;

pour n de 1 jusque p-2 faire u:=irem(u^2-2,M); fpour si u==0 alors Disp "premier" sinon Disp "pas premier" fsi g:; Avec ce programme,xcasmontre que 2444971 est premier en moins de

95 secondes. C'est tout de m^eme un nombre de 13395 chires. C'est avec ce

test que l'actuel record du plus grand nombre premier (connu!) a ete battu en decembre 2017. Il s'agit deM77232917qui a plus de 23 millions de chires.

2 La suite(Ln)

2.1 Son origine

La suite mysterieuse (Ln) est issue d'une suite recurrente double ordi- naire :un+1= 4unun1, avec les valeurs initialesu0= 2 etu1= 4. Dans les articles originaux de Lucas (1878), voir [2] et [3], il etudie systematiquement la divisibilite des termes de ce type de suite par des nombres premiers. On sait calculer les termes d'une telle suite : on introduit l'equation caracteristiqueX24X+ 1 = 0 dont les racines sont= 2 +p3 et 1 =1= 2p3. On a alorsun=n+n. La suite (Ln) n'est autre que la sous-suite de (un) formee des termes d'indice une puissance de 2 :

2.1 Proposition.1) Pour toutn0on a la formule :

L n= (2 +p3)

2n+ (2p3)

2n:

2) En particulier, on aLp2= (2p3)

2p2(2 +p3)

2p1+ 1.

Demonstration.C'est immediat par recurrence, le point crucial est la re- marque (2 +p3)(2p3) = 1.

2.2Remarque.Cette formule vaut dans tout anneau commutatif contenantp3 (c'est-a-dire un element de carre 3). On notera qu'un tel anneau contient

aussi les entiersn= 1 + 1 ++ 1 (nfois), ces entiers pouvant ^etre nuls si la caracteristique est positive.

3 Demonstration du theoreme

3.1 Rappels sur Frobenius

Soitqun nombre premier etFq=Z=qZle corps aqelements. Rappe- lons que dans tout anneauAcontenantFq, donc de caracteristiqueq, on a l'application de FrobeniusF:x7!xqdont on rappelle les proprietes :

1) C'est un homomorphisme d'anneaux deA, en particulier on a (xy)q=

x qyq, ce qui est banal, et (x+y)q=xq+yq, ce qui l'est moins.

2) SiAest un corps niFest un isomorphisme.

3) L'homomorphismeFxe les elements deFqet, reciproquement, siA

est un corps, les points xes deFsont exactement les elements deFq.

3.2 Le sens direct

On suppose queM= 2p1 est premier.

3.2.1 Les carres

On a un premier lemme :

3.1 Lemme.Soitpun nombre premier impair etM= 2p1. On suppose

Mpremier. Alors,3n'est pas un carre moduloM.

2 Demonstration.On peut evidemment montrer ce lemme en utilisant la loi de reciprocite quadratique. La preuve ci-dessous evite le recours a ce theoreme et n'utilise que les notions elementaires sur les carres d'un corps ni qu'on peut trouver dans [4]. CommeMest congru a1 modulo 4,1 n'est pas un carre deFM. Dire que 3 n'est pas un carre est alors equivalent a dire que3 en est un. Mais ceci revient a dire que la racine cubique de l'unite j=12 +p32 est dansFM, ou encore que 3 diviseM1 = 2(2p11) donc que 2 p11 (mod 3). Comme on a 2 1 (mod 3) et quep1 est pair, c'est bien vrai.

3.2Remarque.En revanche, 2 est un carre dansFM. En eet, commeM=

2 p1, on a 2 = 2p+1et 2 est le carre de 2(p+1)=2. On peut aussi, si l'on est plus savant, utiliser le fait que 2 est un carre carMest congru a1 modulo

8, voir [5].

3.2.2 Le corps F

M2 Comme 3 n'est pas un carre deFM, le polyn^omeX23 est irreductible sur F Met on considere son corps de ruptureFM[X]=(X23) qui n'est autre que le corpsFM2. Dans ce corps, on choisit une racine de 3, par exemple l'image deX, qu'on notep3, et les elements deFM2sont de la formea+bp3 avec a;b2FM. On commence par un lemme :

3.3 Lemme.L'automorphisme de FrobeniusF:x7!xMdeFM2n'est autre

que la conjugaison :(a+bp3)

M=abp3.

Demonstration.En eet, il sut de montrer qu'on aF(p3) =p3 car Fxe les elements deFM. Posonsx=p3. On ax2= 32FMdonc F(x)2=F(x2) =F(3) = 3. CommeFM2est un corps, on a doncF(x) =p3 ouF(x) =p3 mais le premier cas est impossible car p3 n'est pas dans F

Men vertu de 3.1.

3.2.3 Le lemme crucial

Vu le point 2) de 2.1, il sut de prouver le lemme suivant :

3.4 Lemme.On suppose queMest premier. On a(2+p3)

2p1=1dans

F M2. Demonstration.Expliquons l'idee de la preuve. Ce qu'on sait bien calculer dansFM2ce sont les puissancesM-iemes avecM= 2p1. On s'en approchera donc si= 2 +p3 est un carre car on aura alors a calculer la puissance 3 2 p-ieme de. On montre que c'est bien le cas en cherchant une racine carree de 2+p3 dansFM2sous la forme=a+bp3. On ab=12aet on en deduit queaverie 4a48a2+ 3 = 0, d'ou, par exemple,a2= 1=2 (2 est un carre dansFMpar 3.2). Une racine de= 2 +p3 est donc=1p2 (1 +p3).

On peut maintenant calculer :

(2 + p3)

2p1=2p1=2p= (1p2

)M+1(1 +p3) M+1: Mais, commex=p2 est dansFMon axM=x, donc le premier terme donne 12 .On a aussi (1+p3)

M= 1+(p3)

M= 1p3 par la remarque 3.3.

En denitive, on a (2 +p3)

2p1=22

=1 comme annonce.

3.3 Le sens reciproque

On suppose queLp2est multiple deM. Supposons queM= 2p1 n'est pas premier et soitqson plus petit facteur premier, de sorte qu'on aq2M. On considere l'anneauA= (Z=qZ)(p3), c'est-a-dire (Z=qZ)[X]=(X23),p3 designant l'image

1deX. L'anneauAest de cardinalq2et les elements

= 2 +p3 et= 2p3 sont inversibles dansAa cause de la formule = 1.

On aLp2= (2p3)

2p2(2 +p3)

2p1+ 1et cet element est nul dans

A(carqdiviseM). Comme 2p3 y est inversible, on a (2 + p3) 2p1=1 dansA, de sorte que 2+p3 est d'ordre 2 pdans le groupe multiplicatif deA. Mais, ce groupe est de cardinalq21< M= 2p1<2p: c'est absurde!

References

[1] Leh merD.H., An extended Theory of Lucas' functions, Annals of Ma- thematics, Vol. 31, N

3 (1930), p. 419-448.

[2]quotesdbs_dbs2.pdfusesText_2