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

Primi b-elitari

Teoria dei numeri 

Si chiamano “primi b-elitari” i numeri primi che hanno tra i residui quadratici solo un numero finito di numeri di Fermat generalizzati con base b fissata. In altre parole sono i primi p per i quali l’equazione x2b2n + 1 mod p ha soluzione solo per un numero finito di valori di n.

Per b = 2 si hanno i primi elitari.

 

La definizione è analoga a quella dei primi elitari, utilizzando i numeri di Fermat generalizzati al posto dei numeri di Fermat.

 

Dalla definizione si ricava facilmente che:

  • nessun primo che divida b è b-elitario;

  • se un primo p è b-elitario in base b, lo è anche in base pb;

  • se un primo p è b-elitario in base b, lo è anche in tutte le basi della forma b + np;

  • se p è un primo di Fermat generalizzato in base b e ordp(b) > 1, p non è b-elitario in base b;

  • se p è un primo che divide il numero di Fermat generalizzato b2n + 1 con n > 2, p non è b-elitario in base b.

 

Tom Müller e Andreas Reinhart dimostrarono nel 2008 che:

  • i resti dei numeri di Fermat generalizzati modulo un primo p sono periodici; se p = 2nk + 1 con k dispari e ordp(b) = 2mh, con h divisore di k e m non maggiore di n, il periodo inizia dal termine b2n + 1 e la lunghezza è ordh(2);

  • la lunghezza del periodo dei resti modulo un primo b-elitario è 1 o pari;

  • la lunghezza del periodo dei resti modulo un primo p b-elitario è 2 se e solo se p è della forma 12n + 1 e b2 + 1 ≡ b mod p, se b non è residuo quadratico modulo p, oppure b2 + 1 ≡ –b mod p, se b è residuo quadratico modulo p;

  • i primi b-elitari in base b con lunghezza del periodo dei resti uguale a b non sono maggiori di b2 + b + 1; in particolare in base 2 l’unico con lunghezza del periodo uguale a 2 è 7;

  • la lunghezza del periodo dei resti modulo un primo b-elitario p non supera (p + 1) / 4;

  • un primo p è b-elitario in base b con periodo di lunghezza 1 se e solo se p ≡ 1 mod 8 e b ≡ ±1 mod p oppure p ≡ 5 mod 8 e b4 ≡ 1 mod p;

  • 3 è b-elitario in base b se e solo se la base b non è un multiplo di 3, nel qual caso il periodo dei resti ha lunghezza 1;

  • 5 è b-elitario in base b se e solo se la base b non è un multiplo di 5, nel qual caso il periodo dei resti ha lunghezza 1;

  • 23 non è b-elitario in alcuna base;

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

  • i primi di Fermat generalizzati con n > 1 non sono b-elitari in nessuna base; in particolare, 17, 257 e 65537 non sono b-elitari in nessuna base;

  • i primi p tali che 2p +1, 4p + 3 e 8p + 7 siano primi (ossia i primi a partire dai quali inizia una catena di Cunningham di prima specie di lunghezza almeno 4) non sono b-elitari in nessuna base;

  • se p è primo e ordp(2) è dispari, i primi della forma 2np + 1 con n > 2 non sono b-elitari in nessuna base;

  • se p = 2nk + 1 è un primo b-elitario con k dispari, la somma delle lunghezze distinte dei periodi dei resti dei numeri di Fermat generalizzati nelle basi in cui è b-elitario è k;

  • se p = 2nk + 1 è un primo b-elitario con k dispari, il numero di basi minori di p nelle quali è b-elitario con lunghezza m del periodo dei resti è 2nm;

  • i primi che sono b-elitari in qualche base sono infiniti.

 

Sembra che la lunghezza del periodo dei resti sia 4 nella stragrande maggioranza dei casi; Tom Müller e Andreas Reinhart trovarono nel 2008 i minimi primi con lunghezze del periodo fino a 12 e dimostrarono che i primi b-elitari con lunghezza del periodo dei resti maggiore di 12 sono maggiori di 104.

 

Sulla base delle loro ricerche, gli stessi matematici avanzarono nel 2008 le seguenti congetture:

  • esiste almeno un primo b-elitario in qualsiasi base; il problema è aperto solo per le basi che sono multiple di 15, perché nelle altre 3 o 5 sono b-elitari;

  • esistono primi b-elitari con periodo dei resti pari arbitrariamente grande;

  • esistono infiniti primi non b-elitari in alcuna base.

 

Nel 2008 Xiaoqin Li dimostrò che:

  • 7 è b-elitario in tutte le basi della forma 7n + 2, 7n + 3, 7n + 4 e 7n + 5;

  • 11 è b-elitario in tutte le basi della forma 11n + 1 e 11n + 10;

  • 13 è b-elitario in tutte le basi della forma 13n + 1, 13n + 5, 13n + 8 e 13 + 12;

  • 19 è b-elitario in tutte le basi della forma 19n + 1, 19n + 7, 19n + 8, 19n + 11, 19n + 12 e 19 + 18;

  • 41 è b-elitario in tutte le basi che non sono della forma 41n + k, con k uguale a 0, 1, 3, 9, 14, 27, 32, 38 o 40;

  • 641 è b-elitario in tutte le basi che non sono della forma 41n + k, con k uguale a 0, 1, 2, 4, 5, 8, 10, 16, 20, 21, 25, 29, 31, 32, 40, 42, 50, 58, 61, 62, 64, 67, 77, 80, 84, 100, 105, 116, 122, 124, 125, 128, 129, 134, 141, 145, 153, 154, 155, 159, 160, 168, 177, 199, 200, 210, 221, 232, 241, 243, 244, 248, 250, 256, 258, 268, 282, 287, 290, 305, 306, 308, 310, 318, 320, 321, 323, 331, 333, 335, 336, 351, 354, 359, 373, 383, 385, 391, 393, 397, 398, 400, 409, 420, 431, 441, 442, 464, 473, 481, 482, 486, 487, 488, 496, 500, 507, 512, 513, 516, 517, 519, 525, 536, 541, 557, 561, 564, 574, 577, 579, 580, 583, 591, 599, 601, 609, 610, 612, 616, 620, 621, 625, 631, 633, 636, 637, 639 o 640.

 

La tabella seguente riporta il minimo primo b-elitario con lunghezza del periodo dei resti uguale a n, per n pari fino a 40 (Tom Müller e Andreas Reinhart, 2008, per n fino a 12; Xiaoqin Li, 2009 per n fino a 40).

n

Minimo primo

Base

2

7

2

4

41

2

6

199

199

8

409

6

10

331

23

12

3121

8

14

32251

247

16

30841

75

18

17443

726

20

36901

298

22

50543

182

24

688297

2935

26

180247

6143

28

117973

432

30

796387

27867

32

47710937?

62792

34

51118471?

106257

36

742073

5369

38

78643351?

661362

40

100663393?

54712

 

Potrebbero esistere primi inferiori a quelli riportati, ma maggiori di 107, con lunghezza del periodo dei resti uguale a 32, 34, 38 e 40 (Xiaoqin Li, 2009).

Bibliografia

  • Müller, Tom;  Reinhart, Andreas;  "On Generalized Elite Primes" in Journal of Integer Sequences, vol. 11, 2008.
  • Xiaoqin, Li;  "Verifying Two Conjectures on Generalized Elite Primes" in Journal of Integer Sequences, vol. 12, 2009.

Contattami

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