[N+] Fibonacci mod p

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-30 22:15, Simo_the_wolf wrote:
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-26 17:19, HiTLeuLeR wrote:
 LA SOLUZIONE DEL PROBLEMA.
 
 Dalla formula di Binet, per ogni n € N: Fn = [1/sqrt(5)] · ([(1+sqrt(5))/2]n - [(1-sqrt(5))/2]n), ovvero: 2n · 5Fn = [1+sqrt(5)]n - [1-sqrt(5)]n.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 C\'è qualcosa che non mi convince... non dovrebbe essere:
 2n · sqrt(5)Fn = [1+sqrt(5)]n - [1-sqrt(5)]n</BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ah, questa mi era sfuggita... Hit, permetti che risponda io?
 
 Hai ragione, ma non fa nulla. Il passaggio incriminato può correggersi così:
 
 2n · 5Fn = sqrt(5){[1+sqrt(5)]n - [1-sqrt(5)]n} = sqrt(5).0 = 0.
 
 Il resto procede senza intoppi.

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Pumf... mi son perso per strada una radice, arrrgh! Provvedo subito ad apportare le dovute correzioni, grazie per la segnalazione.
 
 P.S.: certo che permetto, marco! <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 
 \"Il lavoro non mi piace, non piace a nessuno, ma a me piace quello che c\'è nel lavoro: la possibilità di trovare se stessi.\" - Joseph Conrad

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-29 23:14, Simo_the_wolf wrote:
 Dimostrare che p|Fp-1+Fp+1-1
 
 P.S.: Hit, l\'ho risolto il tuo prob, adesso tu risolvi il mio
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Per verifica diretta: (Fp-1 + Fp+1 - 1)p=2 = 1 + 2 - 1 = 0 mod 2, e così pure analogamente: (Fp-1 + Fp+1 - 1)p=5 = 3 + 8 - 1 = 0 mod 5.
 
 Sia dunque p un primo naturale > 2 e diverso da 5. Coerentemente con le notazioni e le nomenclature ch\'io stesso ho introdotte esponendo la mia soluzione al problema originario di marco, ragioniamo distinguendo fra due possibili casi:
 
 i) se Leg(p,5) = 1: p | Fp-1. Inoltre, in base al teorema di HiTLeuLeR-FeRMaT:
 
 2p+1 · 5Fp+1 =5 sqrt(5) * ([1+sqrt(5)]p+1 - [1-sqrt(5)]p+1) =5
 -2 =5 sqrt(5) * [1+sqrt(5) - 1 + sqrt(5)] =5 10 mod p.
 
 Ergo, per la proprietà (H.1): 2p+1 · 5Fp+1 = 10 mod p, cioè: 10Fp+1 = 10 mod p, e quindi: Fp+1 = 1 mod p, pur di considerare che 10 è primo con p e applicare di conseguenza il 2° teorema di Euclide dell\'Aritmetica. Ne seguita pertanto che:
 Fp-1 + Fp+1 - 1 = Fp+1 - 1 = 1 - 1 = 0 mod p;
 
 ii) se Leg(p,5) = -1: p | Fp+1. Del resto, dal teorema di HiTLeuLeR-FeRMaT:
 
 -2p+1 · 5Fp-1 =5 2p-1 · 5Fp-1 · [1+sqrt(5)] * [1-sqrt(5)] =5
 -2 =5 sqrt(5) * ([1-sqrt(5)] * [1+sqrt(5)]p - [1+sqrt(5)] * [1-sqrt(5)]p) =5
 -2 =5 sqrt(5) * ([1-sqrt(5)]2 - [1+sqrt(5)]2) =5
 -2 =5 sqrt(5) * [6 - 2sqrt(5) - 6 - 2sqrt(5)] = -20 mod p.
 
 Perciò, di nuovo in virtù della proprietà (H.1): -2p+1 · 5Fp-1 = -20 mod p, ovvero: 20Fp-1 = 20 mod p, e quindi: Fp-1 = 1 mod p, a patto di considerare che 20 è primo con p e sfruttare conseguentemente il consueto 2° teorema d\'Euclide dell\'Aritmetica. Da qui: Fp-1 + Fp+1 - 1 = Fp-1 - 1 = 1 - 1 = 0 mod p.
 
 Riassumendo il tutto, ne risulta finalmente la tesi, q.e.d. Alla prossima...
 
 
 \"Prima che me ne dimentichi... \"ottimissimo\" lavoro, simo!!!\" - HiTeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 01-12-2004 22:44 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

ECCO, QUESTA SI\' E\' UNA SOLUZIONE DAVVERO ELEMENTARE...
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-25 17:22, marco wrote:
 Come [quasi] tutti sanno, la successione di Fibonacci è definita come F0 = 0; F1 = 1; Fn+1 = Fn + Fn-1.
 
 Sia p un primo. Si dimostri che vale una delle seguenti:
 
 i) p | Fp-1, oppure
 ii) p | Fp, oppure
 iii) p | Fp+1.
 
 Bonus question: caratterizzare i primi per cui vale ognuno dei tre casi (i)-(iii).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Guardavo Codice Mercury, quando m\'è venuto in mente che... pummmfff!!! Vabbe\', adesso capirete... In base alla formula di Binet, per ogni n € N0:
 
 <center>2n-1 · Fn = sumk=0...Floor((n-1)/2) Bin(n, 2k+1) · 5k,</center>
 ove Floor(·) denota, al solito, la funzione che ad ogni numero reale fa corrispondere la sua parte intera bassa e Bin(a,b) il coefficiente binomiale di ordine a su b, per ogni a € N ed ogni b = 0, 1, ..., n. E allora, se p è un qualsiasi primo intero > 2 e diverso da 5: i) 2p Fp+1 = sumk=0...(p-1)/2 Bin(p+1, 2k+1)·5k;
 ii) 2p-1 · Fp = sumk=0...(p-1)/2 Bin(p, 2k+1) · 5k, e quindi:
 
 <center>i\') Fp+1 = [1 + Leg(p,5)]/2 mod p; oooooii\') Fp = Leg(p,5) mod p,</center>
 ove Leg(p,5) indica, come già in precedenza, il simbolo di Legendre di numeratore p e denumeratore 5. Se dunque Leg(p,5) = -1: p | Fp+1. Se invece Leg(p,5) = 1, allora: Fp-1 = Fp+1 - Fp = 1 - 1 = 0 mod p, ovvero: p | Fp-1. I casi p = 2 e p = 5 sono banali.
 
 EDIT: su segnalazione di marco, apportata una piccola correzione.
 
 
 \"Datemi ascolto, risparmiatevi i complimenti e conservate le forze per il problema che sto per proporvi... Ci sarà da tremare, brrr!!!\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon21.gif"> [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 10:33 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-29 23:14, Simo_the_wolf wrote:
 Dimostrare che p|Fp-1+Fp+1-1
 
 P.S.: Hit, l\'ho risolto il tuo prob, adesso tu risolvi il mio <IMG SRC="images/forum/icons/icon_wink.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Naturalmente, la soluzione al tuo problema adesso diviene banale e immediata, e quindi non mi resta che aggiungerci un \"arrivederci alla prossima\"!!! Anzi, aspetta un attimo... Mo\' che ci ripenso, ci ho giusto il problema che potrebbe fare al caso nostro... Sai, è giusto ch\'io ti ricambi il favore e ti ripaghi del tuo gentil pensiero, tutto qui! Ti va di dedicargli un po\' del tuo tempo? Ok, lo prendo per un \"sì\", ghgh... Be\', dammi qualche minuto e arriva!!! <IMG SRC="images/forum/icons/icon_wink.gif">
 
 
 \"Sii più saggio degli altri, se puoi, ma non glielo dire.\" - Chesterfield [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 22:52 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

HiT\'s HaRDeR: siano p un primo naturale diverso da 5 e q un primo intero > 0 tale che: q | Fp. Si dimostri allora che: q = 1 mod p vel q = - 1 mod p. Si fornisca quindi una caratterizzazione completa dei due casi!!!
 
 NdH: posso dirlo?!? Arrrgh! Vabbe\', me ne sto zitto, occheeeeeeiii...
 
 P.S.: uffi, volevo semplicemente augurarvi buon divertimento, tutto qua!!! <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 
 \"Il tizio che ha inventato la ruota era un idiota. Piuttosto, il tale che ha inventato le altre tre... ecco, quello sì che era un genio.\" - Sid Caesar [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 23:16 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Preciso che non ho avuto ancora modo di riscriverlo per benino e mettere il tutto nero su bianco, ché l\'ho più che altro improvvisato stamane in facoltà, di fronte agli sguardi attoniti degli altri ingegneri (btw, ghgh), dopo due notti e un giorno di intenso lavoro!!! Tuttavia, a una rapidissima occhiata, mi pare che il proof vada sostanzialmente bene. Vi terrò aggiornati, in ogni caso!
 
 P.S.: sboroneggiare è un\'arte, ma io ne ho fatto un esercizio di stile... <IMG SRC="images/forum/icons/icon_razz.gif">
 
 
 \"I numeri sono delle creature meravigliose!\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon_cool.gif"> [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 23:35 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

D\'oooh... Ho riletto tutto il topic per intero e mi sono reso conto che la mia ultima proposta di soluzione ricalca sostanzialmente l\'approccio già suggerito da sprmnt!!! Ahime\', mi ero rifiutato di dargli lettura, per non essere influenzato sulla \"scelta\" della linea dimostrativa, e così... <IMG SRC="images/forum/icons/icon_frown.gif">
 
 
 \"Apprendere e non meditare è vano. Riflettere senza studio è pericoloso.\" - Confucio

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 22:35, HiTLeuLeR wrote:
 ECCO, QUESTA SI\' E\' UNA SOLUZIONE DAVVERO ELEMENTARE...
 [...]
 ii\') Fp = 1 + Leg(p,5) mod p[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 22:51 ]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Beh, che dire?, ottimo lavoro! (così come a Sprmnt) Solo un piccolo errore di stampa: quell\' \"1+\" nel caso (ii\') non c\'è. Nei passaggi successivi, infatti, usi la formula corretta:
 
 Fp = Leg(p,5).
 
 Ciao.
 
 M.[addsig]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Ah, vero... Deve avermi fregato il copincolla!!! Grazie per la segnalazione, marco. Attento e puntuale come sempre... <IMG SRC="images/forum/icons/icon_smile.gif">
 
 P.S.: sono felice di potervi confermare la traccia dell\'ultimo problema!!! Adesso non vi resta che fatigare... Su, Matematici, matematici e aspiranti tali, su... <IMG SRC="images/forum/icons/icon_wink.gif">
 
 
 \"Il grande risultato dell\'umanità attuale è che non abbiamo più bisogno di avere continuamente timore dinanzi alle belve feroci, ai barbari, agli dei e ai nostri sogni.\" - Nietzsche [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 10:30 ]

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-02 23:13, HiTLeuLeR wrote:
 HiT\'s HaRDeR: siano p un primo naturale diverso da 5 e q un primo intero > 0 tale che: q | Fp. Si dimostri allora che: q = 1 mod p vel q = - 1 mod p. Si fornisca quindi una caratterizzazione completa dei due casi!!!
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Harder? Mi sembra piuttosto un facile corollario del problema base...
 
 ----------------
 
 Abbiamo già ampiamente discusso e dimostrato che, per ogni primo q, l\'insieme di numeri di Fibonacci divisibili per q sono cadenzati regolarmente, con periodo almeno pari a 3(*). Sia T tale periodo.
 
 Ho già provato che T | q + 1 - R, dove R è già stato definito a suo tempo, nel corso della \"dimostrazione geometrica\" [Ricordo che vale R = 1 + Leg(q,5)].
 
 Le ipotesi dicono T | p. T > 1, quindi necessariamente T = p. Allora q = R - 1 (p).
 
 Ossia, q = -1 sse R = 0 sse Leg(q,5) = -1; q = 1 sse R = 2 sse Leg(q,5) = +1. Il caso q = 5 è escluso dal fatto che F5=5 e p diverso da 5, per hp. []
 
 
 (*) Quest\'ultimissimo dettaglio non è stato ancora menzionato, e di fatto, mi servirà solo T > 1. Tuttavia segue banalmente dall\'osservazione che F1 = F2 = 1.
 
 Ciao.
 
 M.
 
 \"We shall see. So many strange things have chanced that to learn the prais of a fair lady under the loving strokes of a Dwarf\'s axe will seem no great wonder.\" [ Questo Messaggio è stato Modificato da: marco il 03-12-2004 12:08 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-03 12:04, marco wrote:
 Harder? Mi sembra piuttosto un facile corollario del problema base...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Psicologia, marco, pura e semplice psicologia!!! <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 Le nostre soluzioni sono sostanzialmente identiche, eccetto per il fatto che la tua si poggia sul proof simil-geometrico che tu stesso hai confezionato in relazione al problema originale, la mia invece su considerazioni molto più modeste, nonché (incidentalmente) elementari... <IMG SRC="images/forum/icons/icon_frown.gif">
 
 ---
 
 Per ogni m, n € N: gcd(Fm, Fn) = Fgcd(m,n). Del resto, la soluzione del quesito di apertura ci garantisce che, per ogni primo intero q > 0: q | Fq-Leg(q,5).
 
 A questo punto, se esiste un qualche primo p in N tale che nondimeno q sia un divisore di Fp, allora necessariamente: Fp = gcd(Fp, Fq-Leg(q,5)), poiché q non può dividere F1. Ne seguita che: p | q-Leg(q,5), e quindi: q = pk + Leg(q,5), essendo k € N. Di qui la tesi, supposto p =\\= 5, q.e.d.
 
 
 \"E\' risaputo che la gente si impressiona con poco, gh... Perché dunque non giocherellarci? In fondo, ciascuno si diverte a proprio modo...\" - HiTLeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 14:58 ]

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

Ok, marco mi ha battuto sul tempo... cmq ormai credo manchi una sola cosa da dimostrare che però è stata usata un po\' di volte...
 Lemma. Dimostrare che, per ogni m,n€N si ha mcd(Fn,Fm)=Fmcd(m,n) dove {Fn} è la successione di Fibonacci

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-04 18:14, Simo_the_wolf wrote:
 Lemma. Dimostrare che, per ogni m,n€N si ha mcd(Fn,Fm)=Fmcd(m,n) dove {Fn} è la successione di Fibonacci
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Vedi giornalino 4, problema 25.

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Problema: osservando in questi giorni la sequenza dei numeri dei Fibonacci, ho notato che, se p è un primo intero > 2, p = 1 mod 4 e Leg(p,5) = -1, allora:
 p | F(p+1)/2. Così, per esempio: 13 | F7 e 37 | F19.
 
 Ebbene, di quella che fino a ieri sera sembrava soltanto un\'ulteriore conferma della legge di Guy dei piccoli numeri oggi possiedo un proof decisamente elementare, se non persino banale... Naturalmente, l\'invito è a provare il claim.
 
 Buon divertimento e ciao,
 --- S. Tr.
 
 
 \"Un\'opera è completa soltanto quando l\'obiettivo è raggiunto.\" - Paulo Coelho, L\'Alchimista [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 07-12-2004 14:09 ]