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

Radici primitive

Teoria dei numeri 

Si chiama “radice primitiva” di un intero n ogni numero r primo rispetto a n, tale che rk mod n assume φ(n) valori distinti se k varia da 1 a n – 1; se n è primo, rk mod n assume tutti i valori da 1 a n – 1. Per esempio, 3 è una radice primitiva di 7, perché 31 mod 7 = 3, 32 mod 7 = 2, 33 mod 7 = 6, 34 mod 7 = 4, 35 mod 7 = 5, 36 mod 7 = 1.

 

Quando si scrive che un numero n negativo o maggiore di p è radice primitiva di p, si intende che n mod p è radice primitiva di p. Per esempio, –20 è radice primitiva di 31, perché –20 mod 31 = 11 è radice primitiva di 31 e 15 è radice primitiva di 13 perché 15 mod 13 = 2 è radice primitiva di 13.

 

Hanno radici primitive solo 2, 4 e gli interi della forma pm e 2pm, dove p è un primo dispari (Gauss, Disquisitiones Arithmeticae, 1801); i numeri minori di 100 che ne sono privi sono: 8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 95, 96, 99.

 

Se n ha una radice primitiva, ne ha esattamente φ(φ(n)); in particolare ogni numero primo ha φ(n – 1) radici primitive.

Un intero n è radice primitiva di m, con n e m primi tra loro, se e solo se Condizione necessaria e sufficiente perché n sia radice primitiva di m per ogni primo q che divide φ(m). Questo costituisce un criterio veloce per determinare se un intero sia radice primitiva di un altro o no. Viceversa se esiste un intero n tale che Condizione necessaria e sufficiente perché m sia primo per ogni primo q che divide m – 1, m è primo, ma questo criterio per determinare se un numero sia primo ha utilità pratica solo nei casi nei quali si conosce la scomposizione di m – 1, come per i numeri di Fermat.

 

Il piccolo teorema di Fermat ci assicura che, se p è primo, np – 1 – 1 è multiplo di p. Se p – 1 è il minimo esponente per il quale questo sia vero per n, n è radice primitiva di p.

Per esempio, 6 è radice primitiva di 11, perché 610 – 1 è multiplo di 11 e questo non succede per nessuna potenza di 6 inferiore, mentre 6 non è radice primitiva di 19, perché 618 – 1 multiplo di 19, ma anche 69 – 1 è multiplo di 19.

 

Non si conosce alcun metodo sistematico per trovare una radice primitiva di un intero dato: bisogna procedere per tentativi, anche se di solito ne bastano pochi, perché le radici primitive sono relativamente numerose, come detto sopra.

Trovata una radice primitiva n di p, è semplice trovare tutte le altre: sono tutti e soli i numeri nm mod p, con m e φ(p) primi tra loro.

Per esempio, 2 è una radice primitiva di 13; gli interi minori di 13 e primi rispetto a φ(13) = 12 sono 1, 5, 7 e 11 e quindi le altre radici primitive di 13 sono 25 mod 13 = 6; 27 mod 13 = 11 e 211 mod 13 = 7.

 

Stephen D. Cohen, Tomás Oliveira e Silva e Tim Trudgian dimostrarono nel 2014 che se p ha radici primitive ed è diverso da 3, 5, 7, 11, 13, 19, 31 43, e 61 e a, b e c sono interi minori di p e diversi da zero, esiste almeno una soluzione dell’equazione abr1 + cr2 mod p, con r1 e r2 radici primitive (non necessariamente distinte) di p e in particolare vi sono almeno due radici primitive consecutive (v. congetture sulle radici primitive).

 

W.B. Han dimostrò nel 1989 che se p è una potenza di un primo maggiore di 266 e a, b e c sono interi minori di p, tali che ac(b2 – 4ac) ≠ 0, p ha almeno una radice primitiva r tale che ar2 + br + c sia radice primitiva di p. In particolare ogni primo maggiore di 266 ha almeno una radice primitiva r tale che anche r2 + 1 sia radice primitiva.

 

Se n è radice primitiva di un primo p, è anche radice primitiva di tutte le potenze di p, a meno che np – 1 ≡ 1 mod p2, nel qual caso n + p è radice primitiva di tutte le potenze di p. Quindi se un numero è radice primitiva del quadrato di un primo p, è anche radice primitiva di ogni potenza di p.

Una radice primitiva di un primo p è pertanto molto spesso radice primitiva delle potenze di p; le prime eccezioni sono: 14, radice primitiva di 29, ma non di 292; 18, radice primitiva di 37, ma non di 372 e 19, radice primitiva di 43, ma non di 432.

I primi p inferiori a 1000 che hanno almeno una radice primitiva che non sia radice primitiva di p2 sono (Jud McCranie, The Online Encyclopedia of Integer Sequences, http://oeis.org): 2, 29, 37, 43, 71, 103, 109, 113, 131, 181, 191, 211, 257, 263, 269, 283, 349, 353, 359, 367, 373, 397, 439, 449, 461, 487, 509, 563, 599, 617, 619, 631, 641, 647, 653, 701, 739, 743, 773, 797, 839, 857, 863, 883, 887, 907, 919, 947, 971, 983.

Qui trovate i primi p inferiori a 25000 che hanno almeno una radice primitiva che non sia radice primitiva di p2 (Robert Israel, The Online Encyclopedia of Integer Sequences, http://oeis.org).

 

Gli unici primi p noti per i quali la minima radice primitiva non sia radice primitiva di p2, detti anche “primi non generosi”, sono:

  • 2, la cui minima radice primitiva è 1, che non è radice primitiva di 22 = 4;

  • 40487, la cui minima radice primitiva è 5, che non è radice primitiva di 404872 = 1639197169;

  • 6692367337, la cui minima radice primitiva è 5, che non è radice primitiva di 66923673372 = 44787780573344471569.

 

Se n è radice primitiva di un primo dispari p, quello dei due tra n e n + pk che è dispari è anche radice primitiva di 2pk.

 

Se n è radice primitiva di p, lo è anche l’inverso moltiplicativo di n, vale a dire l’intero k tale che nk ≡ 1 mod p.

 

Se m ha radici primitive, n è una di esse se e solo se è nonresiduo di potenza q-esima, per ogni primo q che divide φ(m); in particolare quindi una radice primitiva di un primo dispari non è mai residuo quadratico dello stesso primo e nessun quadrato è radice primitiva di un primo dispari. Però –n2 con 1 < n < q + 1 è radice primitiva di tutti i primi della forma 2q + 1, se q è un primo dispari. In particolare quindi –4 è radice primitiva di tutti i primi del genere (v. primi di Sophie Germain).

 

Le potenze con esponente pari di una radice primitiva di un intero n sono residui quadratici modulo n , mentre quelle con esponente dispari non lo sono.

 

Se p è primo e dispari:

  • esiste almeno una radice primitiva comune a tutti i numeri pk e 2pk, per ogni valore intero di k > 0;

  • ogni radice primitiva di pk + 1 è anche radice primitiva di pk;

  • esiste almeno una radice primitiva n di p tale che np – 1 non è congruente a 1 modulo p2; per tale radice anche npk – 2(p – 1) non è congruente a 1 modulo p2, per k > 1.

 

Se n è radice primitiva di m, nanb mod m se e solo se ab mod φ(m).

 

Alcune proprietà legate a numeri particolari:

  • ogni non-residuo quadratico è radice primitiva di p se e solo se p è un primo di Fermat;

  • se n è radice primitiva di un primo p della forma 4k + 1, anche = –n lo è;

  • 2 è radice primitiva di tutte le potenze di 3;

  • 3 non è radice primitiva di alcun primo della forma 4k + 3;

  • 3 è radice primitiva di tutti i primi di Fermat;

  • nessun numero di Fibonacci è radice primitiva di 3001;

  • nessun numero di Lucas è radice primitiva di 28657.

 

Se q e p = 2q + 1 sono primi, ossia se q è un primo di Sophie Germain:

  • tutti e soli i nonresidui quadratici di p tranne –1 sono radici primitive di p;

  • se q è della forma 4k + 1, 2 è radice primitiva di p;

  • se q è della forma 4k + 3, –2 è radice primitiva di p;

  • dato un intero n minore di p e diverso da 2, se n è 1 o nq è la minima potenza di n che dia resto 1 se divisa per p e se g2 ≡ g + n mod p, allora g è radice primitiva di p se e solo se lo è g – 1; per esempio, p = 47, n = 4 e g = 20 soddisfano le ipotesi e sia 20 che 19 sono radici primitive di 47.

 

Se q e p = 4q + 1 sono primi:

  • 2 è radice primitiva di p;

  • se q > 3, 3 è radice primitiva di p.

 

Se p è primo e diverso da 3, il prodotto delle sue radici primitive è congruente a 1 modulo p (Gauss).

Se p è primo, la somma delle sue radici primitive è congruente a μ(p – 1) modulo p (Gauss).

 

Se R(p) è il numero di radici primitive di un primo p, la densità asintotica dei primi tali che R(p) / (p – 1) ≤ x è una funzione continua, strettamente crescente, che vale 0 per x = 0 e 1 per x = 1 / 2 (I. Kátai, 1968). Non vale un risultato analogo se si considerano anche i numeri composti che hanno radici primitive (Shuguang Li, 1998).

 

Rappresentando una frazione come numero reale in una base data, prima rispetto al denominatore, si ottengono cifre che si ripetono; per esempio, in base 10 1 / 7; se p è primo, la lunghezza del periodo di 1 / p è un divisore di p – 1. La lunghezza massima del periodo è quindi p – 1 e si ha se e solo se la base è radice primitiva di p (v. primi a lungo periodo).

La lunghezza del periodo dipende dalla base di rappresentazione, così 1 / 7 ha periodo 6 in base 10, ma solo 3 in base 2.

Se n è radice primitiva di p, lo sono anche tutti i numeri della forma kp + n; di conseguenza se la lunghezza del periodo di 1 / p è massima, la lunghezza del periodo nelle basi della forma kp + n è la stessa. Per esempio, 1 / 7 ha periodo di lunghezza 6 in base 10 e in tutte le basi congrue a 10 modulo 7, cioè della forma 7k + 3, come 17 e 24.

 

La tabella seguente mostra le radici primitive dei numeri naturali fino a 20.

n

Radici primitive

1

Nessuna

2

1

3

2

4

3

5

2, 3

6

5

7

3, 5

8

Nessuna

9

2, 5

10

3, 7

11

2, 6, 7, 8

12

Nessuna

13

2, 6, 7, 11

14

3, 5

15

Nessuna

16

Nessuna

17

3, 5, 6, 7, 10, 11, 12, 14

18

5, 11

19

2, 3, 10, 13, 14, 15

20

Nessuna

 

La tabella seguente riporta i numeri naturali inferiori a 100 per i quali n è radice primitiva, per n da –20 a 20 (Vincenzo Librandi e T.D. Noe, The Online Encyclopedia of Integer Sequences, http://oeis.org).

n

Numeri

–20

11, 13, 17, 31, 37, 53, 59, 73, 79

–19

2, 3, 6, 13, 26, 29, 31, 37, 41, 53, 58, 59, 62, 67, 71, 74, 79, 82, 89

–18

5, 7, 23, 29, 31, 37, 47, 53, 61, 71

–17

2, 4, 5, 10, 19, 25, 37, 38, 41, 43, 47, 50, 59, 61, 67, 74, 82, 83, 86, 94, 97

–16

3, 7, 9, 11, 19, 23, 27, 47, 49, 59, 67, 71, 79, 81, 83

–15

2, 11, 13, 22, 26, 29, 37, 41, 43, 58, 59, 71, 73, 74, 82, 86, 89, 97

–14

11, 17, 29, 31, 43, 47, 53, 73, 89, 97

–13

2, 3, 4, 5, 6, 9, 10, 18, 23, 25, 27, 37, 41, 43, 46, 50, 54, 73, 74, 79, 81, 82, 86, 89, 97

–12

5, 17, 23, 25, 41, 47, 53, 59, 71, 83

–11

2, 7, 13, 14, 17, 26, 29, 34, 41, 49, 58, 73, 79, 82, 83, 98

–10

3, 17, 29, 31, 43, 61, 67, 71, 83, 97

–9

2, 4, 7, 11, 14, 19, 22, 23, 31, 38, 43, 46, 47, 49, 59, 62, 71, 79, 83, 86, 94, 98

–8

5, 23, 25, 29, 47, 53, 71

–7

2, 3, 5, 6, 9, 10, 13, 17, 18, 26, 27, 31, 34, 41, 47, 54, 59, 61, 62, 81, 82, 83, 89, 94, 97

–6

13, 17, 19, 23, 41, 47, 61, 67, 71, 89

–5

2, 4, 11, 17, 19, 22, 34, 37, 38, 53, 59, 73, 74, 79, 97

–4

3, 7, 9, 11, 19, 23, 27, 47, 49, 59, 67, 71, 79, 81, 83

–3

2, 5, 10, 11, 17, 22, 23, 25, 29, 34, 46, 47, 50, 53, 58, 59, 71, 83, 89, 94

–2

5, 7, 13, 23, 25, 29, 37, 47, 49, 53, 61, 71, 79

1

2

2

3, 5, 9, 11, 13, 19, 25, 27, 29, 37, 53, 59, 61, 67, 81, 83

3

2, 4, 5, 7, 10, 14, 17, 19, 25, 29, 31, 34, 38, 43, 49, 50, 53, 58, 62, 79, 86, 89, 98

5

3, 6, 7, 9, 14, 17, 18, 23, 27, 34, 37, 43, 46, 47, 49, 53, 54, 73, 74, 81, 83, 86, 94, 97, 98

6

11, 13, 17, 41, 59, 61, 79, 83, 89

7

2, 4, 5, 10, 11, 13, 17, 22, 23, 26, 34, 41, 46, 61, 67, 71, 79, 82, 89, 97

8

3, 5, 11, 25, 29, 53, 59, 83

10

7, 17, 19, 23, 29, 47, 49, 59, 61, 97

11

2, 3, 4, 6, 9, 13, 17, 18, 23, 26, 27, 29, 31, 34, 41, 46, 47, 54, 58, 59, 62, 67, 71, 73, 81, 82, 94

12

5, 7, 17, 25, 31, 41, 43, 49, 53, 67

13

2, 5, 10, 11, 19, 22, 25, 31, 37, 38, 41, 47, 50, 59, 62, 67, 71, 73, 74, 82, 83, 89, 94, 97

14

3, 9, 17, 19, 23, 27, 29, 53, 59, 73, 81, 83, 89, 97

15

2, 4, 13, 19, 23, 26, 29, 37, 38, 41, 46, 47, 58, 73, 74, 82, 83, 89, 94, 97

17

2, 3, 5, 6, 7, 10, 11, 14, 22, 23, 25, 31, 37, 41, 46, 49, 50, 61, 62, 74, 82, 97, 98

18

5, 11, 29, 37, 43, 53, 59, 61, 67, 83

19

2, 4, 7, 11, 13, 14, 22, 23, 26, 29, 37, 41, 43, 46, 47, 53, 58, 74, 82, 83, 86, 89, 94

20

3, 9, 13, 17, 23, 27, 37, 43, 47, 53, 67, 73, 81, 83

 

La tabella seguente riporta i minimi primi che abbiano tra le radici primitive tutti i primi da 2 a pn, per n fino a 19 (Joerg Arndt, The Online Encyclopedia of Integer Sequences, http://oeis.org).

n

pn

Minimo primo

1

2

3

2

3

5

3

5

53

4

7

173

5

11

293

6

13

2477

7

17

9173

8

19

22613

9

23

27653

10

29

61613

11

31

74093

12

37

92333

13

41

170957

14

43

360293

15

47

679733

16

53

847997

17

59

2004917

18

61

69009533

19

67

76553573

 

L’unico intero che abbia tutte le radici primitive consecutive, a parte 2, 3, 4 e 6 che ne hanno una sola, è 5 (M.G. Monzingo, 1976).

Gli unici primi noti privi di radici primitive consecutive sono 2 e 3.

 

E’ stato dimostrato che per ogni primo p maggiore di 61, se a, b e c sono interi minori di p e diversi da zero, esiste almeno una soluzione dell’equazione abr1 + cr2 mod p, con r1 e r2 radici primitive (non necessariamente distinte) di p.

 

Non si conosce alcun quadrato rappresentabile come p + r, dove p è un primo e r una sua radice primitiva, ma non è stato dimostrato che non possano esistere. Gli unici altri interi noti non rappresentabili in questo modo sono: 2, 6, 11, 14, 26, 35, 41, 45, 51; è possibile che non ve ne siano altri.

 

Potrebbero esistere infiniti primi p tali che tutti i primi che dividono p – 1 siano radici primitive di p; quelli inferiori a 10000 sono: 3, 5, 19, 163, 379, 419, 827, 907, 1427, 1787, 1979, 1987, 2083, 2243, 2339, 2539, 2659, 2699, 3083, 3643, 3659, 4723, 5147, 5443, 5563, 5779, 6203, 6299, 6547, 6619, 6803, 6947, 7043, 7283, 7499, 7547, 7883, 7907, 8219, 8387, 8539, 8563, 8627, 8923 (Emmanuel Vantieghem, The Online Encyclopedia of Integer Sequences, http://oeis.org). Se fossero infiniti, esisterebbero infiniti primi con 2 come radice primitiva.

 

Vi sono probabilmente infiniti primi p tali che nessun divisore di p – 1 sia radice primitiva di p; i minimi esempi sono: 17, 41, 73, 89, 97, 113, 137, 193, 233, 241, 251, 257, 281, 307, 313, 337, 353, 401, 409, 433, 439, 449, 457, 499, 521, 569, 577, 593, 601, 617, 641, 643, 673, 727, 761, 769, 809, 857, 881, 919, 929, 937, 953, 977, 997, 1009, 1013, 1033, 1049, 1097, 1129, 1153 (Emmanuel Vantieghem, The Online Encyclopedia of Integer Sequences, http://oeis.org). Se fossero infiniti, esisterebbero infiniti primi che non hanno 2 come radice primitiva.

 

Un problema non risolto è quello di quanto possano essere grandi la minima radice primitiva di un primo p e la differenza tra p e la massima. Ci si aspetta che la minima radice primitiva sia piccola rispetto a p e la massima non troppo più piccola di p; i migliori risultati noti sono:

  • la minima radice primitiva non è maggiore di Limite superiore per la minima radice primitiva di p, per una costante C e qualsiasi ε > 0 (Burgess, 1962);

  • se p < ee24, la minima radice primitiva è minore di p0.499 (Emil Grosswald, 1981);

  • esistono infiniti primi p per i quali la minima radice primitiva è maggiore di Clogp, per ogni costante C (Fridlander, 1949);

  • per ogni intero n, vi sono infiniti primi p tali che la minima radice primitiva sia maggiore di n e minore di pn.

La minima radice primitiva non può essere una potenza.

 

La tabella seguente riporta il minimo numero e il minimo primo per i quali n sia la minima radice primitiva, per n sino a 20.

n

Minimo numero

Minimo primo

1

2

2

2

3

3

3

4

7

4

Nessuno

Nessuno

5

6

23

6

41

41

7

22

71

8

Nessuno

Nessuno

9

Nessuno

Nessuno

10

313

313

11

118

643

12

4111

4111

13

457

457

14

1031

1031

15

439

439

16

Nessuno

Nessuno

17

262

311

18

53173

53173

19

191

191

20

107227

107227

 

La tabella seguente riporta i numeri primi inferiori a 109 che hanno una minima radice primitiva maggiore di 100 (M. Fiorentini, 2014).

Numeri primi

Minima radice primitiva

29418841, 49746649, 75714409, 128373961, 200777329, 251656441, 367101001, 397235281, 416814841, 436741369, 455196361, 471562081, 485632561, 522696001, 553936321, 556589881, 566345641, 627692521, 685754521, 689036041, 698553241, 701892361, 710163169, 748588369, 852120361, 852216121, 894586729, 898716289, 942979129, 944023081, 964518361, 967572841

101

644416081, 822910201

102

49443241, 175245841, 176936761, 267725929, 271086649, 306529129, 323243881, 340133641, 546710641, 715484449, 816080521, 851630641, 855732671, 860531281, 927863161, 939156241

103

338764801

104

578689201

105

152076289, 192969841, 231078961, 445221841, 451410961, 481034401, 563098561, 667186081, 677441521, 705946081, 945963841, 946944769, 967384441

106

33358081, 39244921, 224590081, 234577729, 254960161, 276922801, 285044761, 388928401, 604169281, 672811129, 715065289, 773492281, 869057281, 877463161

107

67992961, 222855361, 254505241, 310075921, 339239449, 399554161, 650686969, 665487601, 749957209, 984189649

109

45024841, 97594561, 194450881, 288940681

111

90441961, 178991569, 255005521, 264254761, 460500769, 547386841, 580094761

113

938553001

116

742221481

118

652802569, 810996481

119

435498457

122

184254841, 256113841, 661381081

127

653866921

130

589462129, 847704001

131

324013369

137

899978641

148

831143041

151

 

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

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