Don't take life too seriously: it's just a temporary situation

Primi elitari

Teoria dei numeri 

Si chiamano “primi elitari” i numeri primi che hanno tra i residui quadratici solo un numero finito di numeri di Fermat. In altre parole sono i primi p per i quali l’equazione x2Fn mod p ha soluzione solo per un numero finito di valori di n, dove Fn = 22n + 1 è un numero di Fermat.

Un primo è invece detto anti-elitario se solo un numero finito di numeri di Fermat è non-residuo quadratico, quindi se la stessa equazione non ha soluzione solo per un numero finito di valori di n.

 

Alexander Aigner fu il primo a studiarli nel 1986, dimostrando che:

  • i resti dei numeri di Fermat modulo un numero primo sono periodici;

  • se p = 2nk + 1 con k dispari è primo, il periodo inizia dopo al massimo n termini e la sua lunghezza è ordp(2) = 2mr, dove r è un divisore di k;

  • un primo p può essere elitario solo se la lunghezza del periodo è un numero pari minore di (p – 1) / 4;

  • non esistono primi elitari della forma 120k + a, se a è 11, 13, 19, 23, 31, 47, 59, 61, 71, 79, 91, 109 o 119.

 

Se il periodo dei resti dei numeri di Fermat contiene solo residui quadratici p è anti-elitario, se contiene solo non-residui, è elitario, altrimenti (ed è il caso più frequente) non appartiene a nessuna delle due categorie.

 

Alain Chaumont e Tom Müller dimostrarono nel 2006 che un primo p esprimibile come 2nk + 1 con k dispari è elitario se e solo se ogni resto dei numeri di Fermat ha ordine rispetto a p (v. funzione ordk) che è multiplo di 2n ed è anti elitario se e solo se nessun resto dei numeri di Fermat ha ordine multiplo di 2n rispetto a p.

 

Aigner trovò i 14 inferiori a 35 • 106; successivi sforzi permisero di determinare che ve ne sono solo 27 inferiori a 2.5 • 1011 e di trovarne alcune decine di altri; la tabella tabella seguente riporta i primi 27 e alcuni di quelli maggiori, insieme con le lunghezze dei relativi periodi.

Primi

Periodo

Scopritore e anno

3

1

Alexander Aigner, 1986

5

1

Alexander Aigner, 1986

7

2

Alexander Aigner, 1986

41

4

Alexander Aigner, 1986

15361

4

Alexander Aigner, 1986

23041

4

Alexander Aigner, 1986

26881

4

Alexander Aigner, 1986

61441

4

Alexander Aigner, 1986

87041

8

Alexander Aigner, 1986

163841

4

Alexander Aigner, 1986

544001

8

Alexander Aigner, 1986

604801

6

Alexander Aigner, 1986

6684673

8

Alexander Aigner, 1986

14172161

4

Alexander Aigner, 1986

159318017

8

Tom Müller, 2005

446960641

4

Tom Müller, 2005

1151139841

4

Alain Chaumont e Tom Müller, 2006

3208642561

4

Alain Chaumont e Tom Müller, 2006

38126223361

4

Alain Chaumont e Tom Müller, 2006

108905103361

4

Alain Chaumont e Tom Müller, 2006

171727482881

8

Alain Chaumont e Tom Müller, 2006

318093312001

4

Tom Müller, 2007

443069456129

8

Tom Müller, 2007

912680550401

4

Tom Müller, 2007

1295536619521

4

Tom Müller, 2007

1825696645121

4

Tom Müller, 2007

2061584302081

4

Tom Müller, 2007

149980257976321

4

Tom Müller, 2007

180143985094819841

4

Tom Müller, 2007

17946844515071426561

4

Tom Müller, 2007

602101726565879764746241

4

Tom Müller, 2007

18689993171242167040957480961

4

Tom Müller, 2007

6698062947509927640804340264693923841

4

Tom Müller, 2007

259594612076645535006939220517547333155553281

4

Tom Müller, 2007

454072790419300285645527076156951501366886401

4

Tom Müller, 2007

5290851798351390340329349160185823767293853697

12

Tom Müller, 2007

427059270551861433160409004921216122839524966401

4

Tom Müller, 2007

703439006817830210817911056046755970898146032091137

8

Tom Müller, 2007

11224332574701334411804299515261053590957561930055680001

4

Tom Müller, 2007

14706610598177589607194988966499920472941345523761899969476611133101548846592554958849

8

Tom Müller, 2007

1513709086553447197663141790899377380925732892851065541666808633995369098218399973326212245052682953126051841

 

Tom Müller, 2007

17049868711270191617314842535675714317881664129477001873865235432002384660841796063192517923820674353847074817

6

Tom Müller, 2007

103651807334710679557592095520476224995558922705672870243370445925061171015500030355557038578280006854916128572390454275825421067476368848060417

8

Tom Müller, 2007

667273752630043339457816407868289297853762852994637583496144800119923209172724901300715429529821408835413006527200665643902004801447870984219525121

4

Tom Müller, 2007

1447982982118094038495413715686599834090891132544948191888559696948847396110642834296497572480093210661708416786112625846961505279877629925974500516661505145613130925011428963890609471780377166926949222816197039712383048790356652227592540276103340370165761

4

Tom Müller, 2007

126790687472559659124561548379963985564523358248669165310710570166401736613613966273860141413037725094721854798381710882931763414280644528940129354831105498458012804159761220200495564242342345852725815897970685216995526790260374817321215255704088754357489259415457119600641

4

Tom Müller, 2007

137919183364164309801871296273897978567815394284001671868877889961162036414631073036332227178993952731902051903584747588416810053565690516946961192391821364486038971293351663099524426150380029659853680217974919513183441878771091410224612452817888715648526133041894951493996049229523702339847230756823684904310358187249465481360677643483891970639071250220350322363751923569296644087687400654117968092857008337802477144167288075210142707313608149730129514332161

4

Tom Müller, 2007

433839202410491211800535428912425473284526795926667331636656450457941949411948779555483529118143242671264381906672644688661484418797117681567479237091819009479079882183579972907404759920970445856772932927501514323200000813356395099010015123186536467070124955609402263567554690926870876718848124438740025469580927747049396436954173958920010243394122525998379562148405321212847707832872961906345585051792940170741816434458668696898533231555889385891936744062415557796078240676983667001040836286113361569605516781416477699385499112002413142112558207243416873558101641054814289230905690363414162206307328719337554278900897690687577100550535574835662765097166353120377807797661011011163929058500030075828183132010718068980022119028440112961076174622748261495398332241925250294209331333315181690142029987799393064190491651043730395891024172628228337800416760057529127403521

4

Tom Müller, 2007

38081531045287243489078262499251063691847636844164409101326683099116463510637707261779241557025623046790600924840014435333079045813023888514443812595367014286191346419468590892685611757545914275539231291611924867949300604709485686638494646666635217775976058529844225321383824315813206206580458987861978853137576564823656255902852423595558753672843857650060387914747248880806172836120163653751288642037497051458975716113144855144309913803982943649068697563563314338807360841276398960271036433494474838824179624704231150629617413012589944560085944786740451459205241761004643704721913394615865266250729612319331483480504348364736950400309315866699341849120663405605567079057434011360018417116231432516742591600012089055857589090571733439079061415798766084294400560343705716500495267158277301026938286268550102285323894697003940199021177462685706106626497052800154390832280890873723944975522600030154983112487135391270188948440984990397110060628445344211513683011592230719240147890700951983845240586103726414175208966637088525678756411872460251011702858010512420576717763668055835401221598963043731401511082917024469240420258497574575293742999957988302207321767068521296035841

4

Tom Müller, 2007

 

Si ritiene che i primi elitari siano infiniti, ma non è stato dimostrato; Tom Müller si spinse addirittura a congetturare che siano infiniti quelli della forma 2n • 15 + 1.

 

M. Křížek, Florian Luca e L. Somer dimostrarono nel 2002 che il numero di primi elitari inferiori a n non cresce più velocemente di c * n / log(n)^2, con c costante, quindi la serie dei reciproci dei primi elitari è convergente.

 

Tom Müller dimostrò nel 2007 che:

  • il numero di primi anti-elitari inferiori a n non cresce più velocemente di c * n / log(n)^2, con c costante;

  • se p = 2nk + 1 è un primo anti-elitario con k dispari, m è la lunghezza del periodo dei resti dei numeri di Fermat modulo p e m > 1, esiste un residuo quadratico r di p tale che Fnr + 1 mod p e che è soluzione dell’equazione Equazione che ha r come soluzione;

  • un primo maggiore di 5 divide un numero di Fermat se e solo se è anti-elitario con periodo di lunghezza 1; dato che i numeri di Fermat sono tutti primi tra loro, hanno, tutti insieme, infiniti fattori primi distinti, quindi il numero di primi anti-elitari con periodo di lunghezza 1 è infinito;

  • un primo è anti-elitario con periodo 2 se e solo se ha la forma 12k + 1 e divide Fn(Fn – 1) + 1 = 22n(22n + 1) + 1; esistono infiniti primi del genere;

  • per ogni intero m esistono primi anti-elitari della forma p = 2nk + 1 con k dispari e n > m;

  • non esistono primi anti-elitari della forma 240k + a, se a è 7, 23, 43, 47, 67, 83, 103, 107, 127, 143, 163, 167, 187, 203, 223 o 227 o della forma 204k + a, se a è 7, 31, 79, 91, 139, 163, 175 o 199.

 

Dato che tutti i fattori primi maggiori di 5 sono anti-elitari e 3 e 5 sono primi elitari, si può affermare che i fattori primi dei numeri di Fermat sono tutti elitari o anti-elitari.

 

La tabella riporta i minimi primi anti-elitari, con le relative lunghezze del periodo.

Primo

Periodo

Scopritore e anno

2

1

Tom Müller, 2007

13

2

Tom Müller, 2007

17

1

Tom Müller, 2007

97

2

Tom Müller, 2007

193

2

Tom Müller, 2007

241

2

Tom Müller, 2007

257

1

Tom Müller, 2007

641

1

Tom Müller, 2007

673

2

Tom Müller, 2007

769

2

Tom Müller, 2007

2689

3

Tom Müller, 2007

5953

5

Tom Müller, 2007

8929

5

Tom Müller, 2007

12289

2

Tom Müller, 2007

40961

4

Tom Müller, 2007

49921

4

Tom Müller, 2007

61681

4

Tom Müller, 2007

65537

1

Tom Müller, 2007

101377

6

Tom Müller, 2007

114689

1

Tom Müller, 2007

274177

1

Tom Müller, 2007

286721

4

Tom Müller, 2007

319489

1

Tom Müller, 2007

414721

4

Tom Müller, 2007

417793

8

Tom Müller, 2007

550801

8

Tom Müller, 2007

786433

2

Tom Müller, 2007

974849

1

Tom Müller, 2007

1130641

12

Tom Müller, 2007

1376257

6

Tom Müller, 2007

1489153

3

Tom Müller, 2007

1810433

8

Tom Müller, 2007

2424833

1

Tom Müller, 2007

3602561

4

Tom Müller, 2007

6700417

1

Tom Müller, 2007

6942721

4

Tom Müller, 2007

7340033

3

Tom Müller, 2007

11304961

4

Tom Müller, 2007

12380161

4

Tom Müller, 2007

13631489

1

Tom Müller, 2007

15790321

3

Tom Müller, 2007

17047297

6

Tom Müller, 2007

22253377

2

Tom Müller, 2007

26017793

1

Tom Müller, 2007

39714817

2

Tom Müller, 2007

45592577

1

Tom Müller, 2007

63766529

1

Tom Müller, 2007

67411969

12

Tom Müller, 2007

89210881

6

Tom Müller, 2007

93585409

6

Tom Müller, 2007

113246209

6

Tom Müller, 2007

119782433

10

Tom Müller, 2007

152371201

2

Tom Müller, 2007

167772161

1

Tom Müller, 2007

171048961

6

Tom Müller, 2007

185602561

12

Tom Müller, 2007

377487361

4

Tom Müller, 2007

394783681

4

Tom Müller, 2007

597688321

2

Tom Müller, 2007

618289153

12

Tom Müller, 2007

663239809

6

Tom Müller, 2007

825753601

1

Tom Müller, 2007

902430721

4

Tom Müller, 2007

1107296257

2

Tom Müller, 2007

1214251009

1

Tom Müller, 2007

2281701377

8

Tom Müller, 2007

3221225473

2

Tom Müller, 2007

4278255361

4

Tom Müller, 2007

4562284561

4

Tom Müller, 2007

5733744641

4

Tom Müller, 2007

6487031809

1

Tom Müller, 2007

6511656961

4

Tom Müller, 2007

7348420609

2

Tom Müller, 2007

11560943617

2

Tom Müller, 2007

15600713729

14

Tom Müller, 2007

23447531521

8

Tom Müller, 2007

29796335617

2

Tom Müller, 2007

30450647041

10

Tom Müller, 2007

46908728641

4

Tom Müller, 2007

48919385089

3

Tom Müller, 2007

70525124609

1

Tom Müller, 2007

74490839041

2

Tom Müller, 2007

77309411329

2

Tom Müller, 2007

83751862273

12

Tom Müller, 2007

96645260801

4

Tom Müller, 2007

107767726081

3

Dennis Martin, 2008

137603804161

4

Dennis Martin, 2008

190274191361

1

Dennis Martin, 2008

206158430209

2

Dennis Martin, 2008

246423748609

2

Dennis Martin, 2008

448203325441

2

Dennis Martin, 2008

529566400513

6

Dennis Martin, 2008

646730219521

1

Dennis Martin, 2008

1084521185281

6

Dennis Martin, 2008

1753340313601

4

Dennis Martin, 2008

2115221118977

3

Dennis Martin, 2008

2422022479873

2

Dennis Martin, 2008

2710954639361

1

Dennis Martin, 2008

2748779069441

1

Dennis Martin, 2008

4485296422913

1

Dennis Martin, 2008

5469640851457

2

Dennis Martin, 2008

 

Bibliografia

  • Aigner, Alexander;  "Über Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind" in Monatsh. Math, n. 101, 1986, pag. 85 – 93.
  • Chaumont, Alain;  Müller, Tom;  "All Elite Primes Up to 250 Billion" in Journal of Integer Sequences, vol. 9, 2006.
  • Müller, Tom;  "On Anti-Elite Prime Numbers" in Journal of Integer Sequences, vol. 10, 2007.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.