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

Radici primitive di Fibonacci

Sequenze  Teoria dei numeri 

Una radice primitiva n di un intero p si dice “radice primitiva di Fibonacci” se n2n + 1 mod p.

Per esempio, le radici primitive di 11 sono 2, 6, 7 e 8 e tra queste 8 è l’unica di Fibonacci, perché 82 ≡ 8 + 1 mod 11.

 

Dalla definizione segue che nknk – 1 + 1 mod p e quindi nkFkn + Fk – 1 mod p.

 

Hanno radici primitive di Fibonacci tutti e sole le potenze dei numeri primi p (incluso p stesso) tali che i resti dei numeri di Fibonacci modulo p abbiano periodo minimo p – 1, ossia che abbiano numero di Pisano p – 1.

 

Daniel Shanks dimostrò nel 1972 che:

  • possono avere radici primitive di Fibonacci solo 5 e i numeri della forma 10k ± 1;

  • se q è potenza di un primo p della forma 4k + 1 diverso da 5, può avere fino a due radici primitive di Fibonacci; se ne ha due, la loro somma è q + 1;

  • se q è potenza di un primo p della forma 4k + 3, può avere al massimo una radice primitiva di Fibonacci.

 

Shanks avanzò la congettura che la frazione dei primi che hanno radici primitive di Fibonacci tenda a Densità asintotica supposta per i primi con radici primitive di Fibonacci, dove C è la costante di Artin. Non è però neppure stato dimostrato che i primi che hanno radici primitive di Fibonacci siano infiniti.

 

Michael E. Mays dimostrò nel 1980 che se p = 60k + 1 e q = 30k + 1 sono entrambi primi, p ha una radice primitiva di Fibonacci. Se la congettura di Dickson fosse vera, questo dimostrerebbe l’esistenza di infiniti primi con radici primitive di Fibonacci.

 

La tabella seguente mostra i primi inferiori a 1000 che hanno radici primitive di Fibonacci e le corrispondenti radici (M. Fiorentini, 2014).

Primi

Radici primitive di Fibonacci

5

3

11

8

19

15

31

13

41

7, 35

59

34

61

18, 44

71

63

79

30

109

11, 99

131

120

149

41, 109

179

105

191

89

239

224

241

52, 190

251

134

269

72, 198

271

255

311

59

359

106

379

360

389

152, 238

409

130, 280

419

399

431

341

439

370

449

166, 284

479

229

491

74

499

275

569

233, 337

571

298

599

575

601

137, 465

631

110

641

279, 363

659

201

701

27, 675

719

330

739

119

751

541

821

213, 609

839

498

929

31, 899

971

798

 

R.A. Mollin studiò nel 1986 una generalizzazione del concetto, definendo radice primitiva di n-Fibonacci come una radice primitiva m di un primo dispari p, tale che m2m + n mod p, dimostrando che:

  • se –n non è un residuo quadratico modulo p, p ha al massimo una radice primitiva di n-Fibonacci, altrimenti ne ha al massimo due;

  • se m è radice primitiva di n-Fibonacci di p, p è della forma 4n – 1 oppure 4n + 1 è residuo quadratico modulo p;

  • se m è radice primitiva di n-Fibonacci di p, mkmk – 1 + 1 mod p e quindi mkUk mod p; dove Uk è un elemento della sequenza di Fibonacci generalizzata definita dalla ricorrenza U0 = 1, U1 = m, Uk = Uk – 1 + nUk – 2.

Mollin dimostrò anche che se q e p = 2q + 1 sono primi, ossia se q è un primo di Sophie Germain, n è un intero minore di p e diverso da 2 e se n è 1 o nq è la minima potenza di n che dia resto 1 se divisa per p, allora:

  • se 4n + 1 è residuo quadratico di p, p ha una radice primitiva di n-Fibonacci;

  • se m è radice primitiva di n-Fibonacci di p, m – 1 e mn – 1 sono radici primitive di p.

 

 

Bibliografia

  • Shanks, Daniel;  "Fibonacci primitive roots" in Fibonaccy Quarterly, n. 10, 1972, pag. 163 – 168, 181.

Contattami

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