Resto del p-esimo fibonacci modulo p

[edriv]

Sia $ ~ F_0=0, F_1=1, F_n + F_{n+1} = F_{n+2} $ la nota successione di Fibonacci, e sia $ ~ p>5 $ un numero primo.

Dimostrare che:
se $ ~ p \equiv 1 \pmod 5 $, $ ~ p \equiv 4 \pmod 5 $ allora $ ~ F_p \equiv 1 \pmod p $
se $ ~ p \equiv 2 \pmod 5 $, $ ~ p \equiv 3 \pmod 5 $ allora $ ~ F_p \equiv -1 \pmod p $

Per i metodi che usa non direi che è "for beginners"... quindi invito tutti gli olimpionici a risolverlo! e leggetevi le ultime pagine della dispensa "zeta-trucchi" di fph

[HiTLeuLeR]

A partire dalla formula di Binet per l'n-esimo numero di Fibonacci (son solo conti): $ \displaystyle 2^{p-1} F_p = \sum_{k=0}^{(p-1)/2} \binom{p}{2k+1} 5^k $, e perciò (piccolo teorema di Fermat): $ F_p \equiv 5^{(p-1)/2} \bmod p $, a patto di considerare che $ \displaystyle\binom{p}{k} \equiv 0 \bmod p $, per ogni $ k = 1, 2, \ldots, p-1 $. Dunque $ F_p $ è congruo a $ \pm 1 \bmod p $ a seconda che $ 5 $ sia o non sia, rispettivamente, un residuo quadratico $ \mod\;\! p $. I.e. a seconda che $ p \equiv \pm 1 \bmod 5 $ oppure $ p \equiv \pm 2 \bmod 5 $, ordinatamente nei due casi.

[HiTLeuLeR]

Per i metodi che usa non direi che è "for beginners"... quindi invito tutti gli olimpionici a risolverlo!

Estensioni di campo? Mio Dio, che spropositi!

[edriv]

Per i metodi che usa non direi che è "for beginners"... quindi invito tutti gli olimpionici a risolverlo!

Estensioni di campo? Mio Dio, che spropositi!

Hai perfettamente ragione.
Soluzione istruttiva

P.S. Come dimostri che 5 è un residuo quadratico mod p sse p è 1 o 4 modulo 5? Reciprocità quadratica o c'è un modo più semplice?

[HiTLeuLeR]

P.S. Come dimostri che 5 è un residuo quadratico mod p sse p è 1 o 4 modulo 5? Reciprocità quadratica o c'è un modo più semplice?

La legge di reciprocità quadratica funziona alla grande, tanto più coi primi $ \equiv 1 \bmod 4 $. E poi non mi sembra che applicarla richieda uno sforzo assai più grande di quello necessario per usare la formula risolutiva della mitica equazione di secondo grado $ ax^2 + bx + c = 0 $. Non sei d'accordo?

[edriv]

P.S. Come dimostri che 5 è un residuo quadratico mod p sse p è 1 o 4 modulo 5? Reciprocità quadratica o c'è un modo più semplice?

La legge di reciprocità quadratica funziona alla grande, tanto più coi primi $ \equiv 1 \bmod 4 $. E poi non mi sembra che applicarla richieda uno sforzo assai più grande di quello necessario per usare la formula risolutiva della mitica equazione di secondo grado $ ax^2 + bx + c = 0 $. Non sei d'accordo?

Come potrei non esserlo!
Considerando anche il fatto che, se avessi menzionato esplicitamente tale legge, il numero di righe della tua dimostrazione (sul mio computer) sarebbe stato un residuo quadratico modulo 5.

[HiTLeuLeR]

[...] se avessi menzionato esplicitamente tale legge, il numero di righe della tua dimostrazione (sul mio computer) sarebbe stato un residuo quadratico modulo 5.

Troppe in ogni caso, per ritenerla una buona soluzione.