OliForum Matematico

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

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.

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

Estensioni di campo? Mio Dio, che spropositi!

HiTLeuLeR ha scritto:

edriv ha scritto: 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?

edriv ha scritto: 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?

HiTLeuLeR ha scritto:

edriv ha scritto: 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.

edriv ha scritto:[...] 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.