Primi di Mersenne e numeri di Fibonacci

[piever]

1) Sia $ p>3 $ un primo di Mersenne ($ p=2^q-1 $)

Determinare $ L_{q-2}\pmod p $

$ L_n $ e' definito come segue:

$ L_0=4 $, $ L_n=L^2_{n-1}-2 $

2) Sia $ p>5 $ un primo.

Determinare $ F_{p^2-1}\pmod p $

$ F_n $ e' definito come segue:

$ F_0=0 $, $ F_1=1 $, $ F_n=F_{n-1}+F_{n-2} $

[Marco]

2)

Boh, forse ne esiste una soluzione diretta, comunque a suo tempo sul Forum si dimostrò che
$ p | F_{p-1} $ sse 5 è un residuo quadratico non nullo mod p
$ p | F_{p+1} $ sse 5 non è un residuo quadratico mod p;
per ogni p diverso da 2 e 5.

Questo implica la tesi.

[piever]

Bah, come sei noioso

Allora propongo una cosa leggermente piu' forte, spero non ancora dimostrata sul forum

Il caso in cui 5 e' un residuo quaratico non e' molto interessante..

Invece:

Sia p un primo dispari tale che 5 non e' un residuo quadratico modulo p.

Dimostrare che $ \forall n\in\mathbb{N} $ si ha:

$ \displaystyle F_n + F_{n+p+1}\equiv 0\pmod p $

E che:

$ \displaystyle p|F_{\frac{p+1}{2}}\Leftrightarrow 4|p-1 $

Colgo l'occasione per uppare il problema 1), molto piu' carino di questo (e anche un po' meno facile)...

[edriv]

Sacrifichiamo il problema 1 in onore dei primi con 9.808.358 cifre...

Posto $ ~ a = 2 + \sqrt 3 $ e $ ~ a' = 2 - \sqrt 3 $, vediamo che soddifano $ ~ aa' = 1, a+a' = 4 $, e quindi per induzione che:
$ ~ L_n = a^{2^n} + a'^{2^n} $.

Chiediamoci se 3 è un residuo quadratico modulo p. 3 è congruo a 3 modulo 4, p è congruo a 3 modulo 4, p è congruo a 1 modulo 3, quindi p è un residuo modulo 3, quindi, per la reciprocità quadratica, 3 non è un residuo modulo p.
D'ora in poi quindi lavoreremo nel campo $ ~ \mathbb{Z}_p[\sqrt 3] $, che per quando appena osservato è diverso da $ ~ \mathbb{Z}_p $. La nostra tesi è che $ ~ p \mid L_{q-2} $, che è equivalente a dimostrare che:
$ ~ a^{2^{q-2}} + a'^{2^{q-2}} = 0 $ (sempre in $ ~ \mathbb{Z}_p[\sqrt 3] $).
Moltiplicando per $ ~ a^{2^{q-2}} $, è equivalente a $ ~ a^{2^{q-1}} = -1 $, ovvero $ ~ (2 + \sqrt 3)^{\frac{p+1}2} = -1 $.
Sappiamo che nel nostro bel campo a caratteristica p, $ ~ (x+y)^p = x^p + y^p $ (basta sviluppare il binomiale), questo ci suggerisce (o almeno dovrebbe suggerirci, io ci sono arrivato dopo giorni), che dobbiamo sbarazzarci di quel "mezzi". In questo modo:
$ ~ 2 + \sqrt 3 = \frac 12 (1 + \sqrt 3)^2 $.

Quindi basta dimostrare che $ ~ \frac 12^{\frac{p+1}2} (1 + \sqrt 3)^{p+1} = -1 $. Lo possiamo riscrivere come:
$ ~ \frac 12 \cdot \frac 12 ^{\frac{p-1}2} \cdot (1 + \sqrt 3)(1^p + \sqrt 3 ^ p) $.
Ora, poichè p è congruo a -1 modulo 8, 2 è un residuo quadratico, quindi anche 1/2. Per il criterio di Eulero quindi: $ ~ \frac 12 ^{\frac{p-1}2} = 1 $. Inoltre, $ ~ \sqrt 3 ^p $ lo riscriviamo come $ ~ \sqrt 3 \cdot 3^{\frac{p-1}2} $ che, poichè 3 non è un residuo, fa $ ~ - \sqrt 3 $.

Quello che ci resta è:
$ ~ \frac 12 \cdot 1 \cdot (1 + \sqrt 3) \cdot (1-\sqrt 3) $
che, senza altri problemi, fa -1.

[wolverine]

Sia p un primo dispari tale che 5 non e' un residuo quadratico modulo p.

Dimostrare che $ \forall n\in\mathbb{N} $ si ha:

$ \displaystyle F_n + F_{n+p+1}\equiv 0\pmod p $

Poniamo $ G_n=F_n + F_{n+p+1} $. Allora $ G_n $ soddisfa la ricorsione di Fibonacci e per dimostrare che $ G_n\equiv 0\pmod p $ per ogni $ n $, basta dimostrare che $ G_0\equiv 0\pmod p $ e $ G_1\equiv 0\pmod p $, ovvero che $ F_{p+1}\equiv 0\pmod p $ e $ F_{p+2}\equiv -1\pmod p $. Questa coppia di congruenze (per la relazione ricorsiva) e' equivalente a $ F_{p}\equiv -1\pmod p $ e $ F_{p+1}\equiv 0\pmod p $, ed e' immediato verificare che queste ultime due sono soddisfatte quando 5 non e' un residuo quadratico modulo $ p $.

E che:
$ \displaystyle p|F_{\frac{p+1}{2}}\Leftrightarrow 4|p-1 $

Questo invece si dimostra con lo stesso ragionamento che porta a concludere che $ p\vert F_{p+1} $ se e solo se 5 non e' un residuo quadratico mod p, ricordandosi che -1 e' un residuo quadratico mod p se e solo se $ p\equiv 1 \pmod 4 $