[N+] Fibonacci mod p

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-30 22:15, Simo_the_wolf wrote:
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-26 17:19, HiTLeuLeR wrote:
<BR><!-- BBCode Start --><B>LA SOLUZIONE DEL PROBLEMA.</B><!-- BBCode End -->
<BR>
<BR>Dalla formula di Binet, per ogni n € N: F<sub>n</sub> = [1/sqrt(5)] · ([(1+sqrt(5))/2]<sup>n</sup> - [(1-sqrt(5))/2]<sup>n</sup>), ovvero: 2<sup>n</sup> · 5F<sub>n</sub> = [1+sqrt(5)]<sup>n</sup> - [1-sqrt(5)]<sup>n</sup>.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>C\'è qualcosa che non mi convince... non dovrebbe essere:
<BR>2<sup>n</sup> · <!-- BBCode Start --><B>sqrt(5)</B><!-- BBCode End -->F<sub>n</sub> = [1+sqrt(5)]<sup>n</sup> - [1-sqrt(5)]<sup>n</sup
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ah, questa mi era sfuggita... Hit, permetti che risponda io?
<BR>
<BR>Hai ragione, ma non fa nulla. Il passaggio incriminato può correggersi così:
<BR>
<BR>2<sup>n</sup> · 5F<sub>n</sub> = <!-- BBCode Start --><B>sqrt(5){</B><!-- BBCode End -->[1+sqrt(5)]<sup>n</sup> - [1-sqrt(5)]<sup>n</sup><!-- BBCode Start --><B>}</B><!-- BBCode End --> = <!-- BBCode Start --><B>sqrt(5)</B><!-- BBCode End -->.0 = 0.
<BR>
<BR>Il resto procede senza intoppi.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

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.
<BR>
<BR>P.S.: certo che permetto, marco! <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>
<BR>\"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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-29 23:14, Simo_the_wolf wrote:
<BR>Dimostrare che p|F<sub>p-1</sub>+F<sub>p+1</sub>-1
<BR>
<BR>P.S.: Hit, l\'ho risolto il tuo prob, adesso tu risolvi il mio
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Per verifica diretta: (F<sub>p-1</sub> + F<sub>p+1</sub> - 1)<sub>p=2</sub> = 1 + 2 - 1 = 0 mod 2, e così pure analogamente: (F<sub>p-1</sub> + F<sub>p+1</sub> - 1)<sub>p=5</sub> = 3 + 8 - 1 = 0 mod 5.
<BR>
<BR>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:
<BR>
<BR>i) se Leg(p,5) = 1: p | F<sub>p-1</sub>. Inoltre, in base al teorema di HiTLeuLeR-FeRMaT:
<BR>
<BR>2<sup>p+1</sup> · 5F<sub>p+1</sub> =<sub>5</sub> sqrt(5) * ([1+sqrt(5)]<sup>p+1</sup> - [1-sqrt(5)]<sup>p+1</sup>) =<sub>5</sub>
<BR><font color=white>-2 </font>=<sub>5</sub> sqrt(5) * [1+sqrt(5) - 1 + sqrt(5)] =<sub>5</sub> 10 mod p.
<BR>
<BR><!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, per la proprietà (H.1): 2<sup>p+1</sup> · 5F<sub>p+1</sub> = 10 mod p, cioè: 10F<sub>p+1</sub> = 10 mod p, e quindi: F<sub>p+1</sub> = 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:
<BR>F<sub>p-1</sub> + F<sub>p+1</sub> - 1 = F<sub>p+1</sub> - 1 = 1 - 1 = 0 mod p;
<BR>
<BR>ii) se Leg(p,5) = -1: p | F<sub>p+1</sub>. Del resto, dal teorema di HiTLeuLeR-FeRMaT:
<BR>
<BR>-2<sup>p+1</sup> · 5F<sub>p-1</sub> =<sub>5</sub> 2<sup>p-1</sup> · 5F<sub>p-1</sub> · [1+sqrt(5)] * [1-sqrt(5)] =<sub>5</sub>
<BR><font color=white>-2</font> =<sub>5</sub> sqrt(5) * ([1-sqrt(5)] * [1+sqrt(5)]<sup>p</sup> - [1+sqrt(5)] * [1-sqrt(5)]<sup>p</sup>) =<sub>5</sub>
<BR><font color=white>-2</font> =<sub>5</sub> sqrt(5) * ([1-sqrt(5)]<sup>2</sup> - [1+sqrt(5)]<sup>2</sup>) =<sub>5</sub>
<BR><font color=white>-2</font> =<sub>5</sub> sqrt(5) * [6 - 2sqrt(5) - 6 - 2sqrt(5)] = -20 mod p.
<BR>
<BR>Perciò, di nuovo in virtù della proprietà (H.1): -2<sup>p+1</sup> · 5F<sub>p-1</sub> = -20 mod p, ovvero: 20F<sub>p-1</sub> = 20 mod p, e quindi: F<sub>p-1</sub> = 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: F<sub>p-1</sub> + F<sub>p+1</sub> - 1 = F<sub>p-1</sub> - 1 = 1 - 1 = 0 mod p.
<BR>
<BR>Riassumendo il tutto, ne risulta finalmente la tesi, q.e.d. Alla prossima...
<BR>
<BR>
<BR>\"Prima che me ne dimentichi... \"<!-- BBCode Start --><I>ottimissimo</I><!-- BBCode End -->\" lavoro, simo!!!\" - HiTeuLeR<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 01-12-2004 22:44 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Start --><B>ECCO, <!-- BBCode Start --><I>QUESTA</I><!-- BBCode End --> SI\' E\' UNA SOLUZIONE <!-- BBCode Start --><I>DAVVERO</I><!-- BBCode End --> ELEMENTARE...</B><!-- BBCode End -->
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-25 17:22, marco wrote:
<BR>Come [quasi] tutti sanno, la successione di Fibonacci è definita come F<sub>0</sub> = 0; F<sub>1</sub> = 1; F<sub>n+1</sub> = F<sub>n</sub> + F<sub>n-1</sub>.
<BR>
<BR>Sia p un primo. Si dimostri che vale una delle seguenti:
<BR>
<BR>i) p | F<sub>p-1</sub>, oppure
<BR>ii) p | F<sub>p</sub>, oppure
<BR>iii) p | F<sub>p+1</sub>.
<BR>
<BR>Bonus question: caratterizzare i primi per cui vale ognuno dei tre casi (i)-(iii).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Guardavo <!-- BBCode Start --><I>Codice Mercury</I><!-- BBCode End -->, quando m\'è venuto in mente che... pummmfff!!! Vabbe\', adesso capirete... In base alla formula di Binet, per ogni n € N<sub>0</sub>:
<BR>
<BR><center>2<sup>n-1</sup> · F<sub>n</sub> = sum<sub>k=0...Floor((n-1)/2)</sub> Bin(n, 2k+1) · 5<sup>k</sup>,</center>
<BR>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) 2<sup>p</sup> F<sub>p+1</sub> = sum<sub>k=0...(p-1)/2</sub> Bin(p+1, 2k+1)·5<sup>k</sup>;
<BR>ii) 2<sup>p-1</sup> · F<sub>p</sub> = sum<sub>k=0...(p-1)/2</sub> Bin(p, 2k+1) · 5<sup>k</sup>, e quindi:
<BR>
<BR><center>i\') F<sub>p+1</sub> = [1 + Leg(p,5)]/2 mod p; <font color=white>ooooo</font>ii\') F<sub>p</sub> = Leg(p,5) mod p,</center>
<BR>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 | F<sub>p+1</sub>. Se invece Leg(p,5) = 1, allora: F<sub>p-1</sub> = F<sub>p+1</sub> - F<sub>p</sub> = 1 - 1 = 0 mod p, ovvero: p | F<sub>p-1</sub>. I casi p = 2 e p = 5 sono banali.
<BR>
<BR>EDIT: su segnalazione di marco, apportata una <!-- BBCode Start --><I>piccola</I><!-- BBCode End --> correzione.
<BR>
<BR>
<BR>\"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"><font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 10:33 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-29 23:14, Simo_the_wolf wrote:
<BR>Dimostrare che p|F<sub>p-1</sub>+F<sub>p+1</sub>-1
<BR>
<BR>P.S.: Hit, l\'ho risolto il tuo prob, adesso tu risolvi il mio <IMG SRC="images/forum/icons/icon_wink.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>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">
<BR>
<BR>
<BR>\"Sii più saggio degli altri, se puoi, ma non glielo dire.\" - Chesterfield<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 22:52 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Start --><B><font color=red>HiT\'s HaRDeR:</font></B><!-- BBCode End --> siano p un primo naturale diverso da 5 e q un primo intero > 0 tale che: q | F<sub>p</sub>. Si dimostri allora che: q = 1 mod p <!-- BBCode Start --><I>vel</I><!-- BBCode End --> q = - 1 mod p. Si fornisca quindi una caratterizzazione completa dei due casi!!!
<BR>
<BR>NdH: posso dirlo?!? Arrrgh! Vabbe\', me ne sto zitto, occheeeeeeiii...
<BR>
<BR>P.S.: uffi, volevo semplicemente augurarvi buon divertimento, tutto qua!!! <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>
<BR>\"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<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 23:16 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

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 <!-- BBCode Start --><I>altri</I><!-- BBCode End --> ingegneri (btw, ghgh), dopo due notti e un giorno di intenso lavoro!!! Tuttavia, a una rapidissima occhiata, mi pare che il <!-- BBCode Start --><I>proof</I><!-- BBCode End --> vada sostanzialmente bene. Vi terrò aggiornati, in ogni caso!
<BR>
<BR>P.S.: sboroneggiare è un\'arte, ma io ne ho fatto un esercizio di stile... <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"I numeri sono delle creature meravigliose!\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon_cool.gif"> <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 23:35 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

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">
<BR>
<BR>
<BR>\"Apprendere e non meditare è vano. Riflettere senza studio è pericoloso.\" - Confucio

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-02 22:35, HiTLeuLeR wrote:
<BR><!-- BBCode Start --><B>ECCO, <!-- BBCode Start --><I>QUESTA</I><!-- BBCode End --> SI\' E\' UNA SOLUZIONE <!-- BBCode Start --><I>DAVVERO</I><!-- BBCode End --> ELEMENTARE...</B><!-- BBCode End -->
<BR>[...]
<BR>ii\') F<sub>p</sub> = <font color=red>1 + </font>Leg(p,5) mod p[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 02-12-2004 22:51 ]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>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:
<BR>
<BR>F<sub>p</sub> = Leg(p,5).
<BR>
<BR>Ciao.
<BR>
<BR>M.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Ah, vero... Deve avermi fregato il <!-- BBCode Start --><I>copincolla</I><!-- BBCode End -->!!! Grazie per la segnalazione, marco. Attento e puntuale come sempre... <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>P.S.: sono felice di potervi confermare la traccia dell\'ultimo problema!!! Adesso non vi resta che <!-- BBCode Start --><I>fatigare</I><!-- BBCode End -->... Su, Matematici, matematici e aspiranti tali, su... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>
<BR>\"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<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 10:30 ]

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-02 23:13, HiTLeuLeR wrote:
<BR><!-- BBCode Start --><B><font color=red>HiT\'s HaRDeR:</font></B><!-- BBCode End --> siano p un primo naturale diverso da 5 e q un primo intero > 0 tale che: q | F<sub>p</sub>. Si dimostri allora che: q = 1 mod p <!-- BBCode Start --><I>vel</I><!-- BBCode End --> q = - 1 mod p. Si fornisca quindi una caratterizzazione completa dei due casi!!!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Harder? Mi sembra piuttosto un facile corollario del problema base...
<BR>
<BR>----------------
<BR>
<BR>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.
<BR>
<BR>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)].
<BR>
<BR>Le ipotesi dicono T | p. T > 1, quindi necessariamente T = p. Allora q = R - 1 (p).
<BR>
<BR>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 F<sub>5</sub>=5 e p diverso da 5, per hp. []
<BR>
<BR>
<BR>(*) Quest\'ultimissimo dettaglio non è stato ancora menzionato, e di fatto, mi servirà solo T > 1. Tuttavia segue banalmente dall\'osservazione che F<sub>1</sub> = F<sub>2</sub> = 1.
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>\"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.\"<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 03-12-2004 12:08 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-03 12:04, marco wrote:
<BR>Harder? Mi sembra piuttosto un facile corollario del problema base...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Psicologia, marco, pura e semplice psicologia!!! <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>Le nostre soluzioni sono sostanzialmente identiche, eccetto per il fatto che la tua si poggia sul <!-- BBCode Start --><I>proof</I><!-- BBCode End --> 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">
<BR>
<BR>---
<BR>
<BR>Per ogni m, n € N: gcd(F<sub>m</sub>, F<sub>n</sub>) = F<sub>gcd(m,n)</sub>. Del resto, la soluzione del quesito di apertura ci garantisce che, per ogni primo intero q > 0: q | F<sub>q-Leg(q,5)</sub>.
<BR>
<BR>A questo punto, se esiste un qualche primo p in N tale che nondimeno q sia un divisore di F<sub>p</sub>, allora necessariamente: F<sub>p</sub> = gcd(F<sub>p</sub>, F<sub>q-Leg(q,5)</sub>), poiché q non può dividere F<sub>1</sub>. 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.
<BR>
<BR>
<BR>\"E\' risaputo che la gente si impressiona con poco, gh... Perché dunque non giocherellarci? In fondo, ciascuno si diverte a proprio modo...\" - HiTLeuLeR <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 03-12-2004 14:58 ]

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

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...
<BR><!-- BBCode Start --><B>Lemma.</B><!-- BBCode End --> Dimostrare che, per ogni m,n€N si ha mcd(F<sub>n</sub>,F<sub>m</sub>)=F<sub>mcd(m,n)</sub> dove {F<sub>n</sub>} è la successione di Fibonacci

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-04 18:14, Simo_the_wolf wrote:
<BR><!-- BBCode Start --><B>Lemma.</B><!-- BBCode End --> Dimostrare che, per ogni m,n€N si ha mcd(F<sub>n</sub>,F<sub>m</sub>)=F<sub>mcd(m,n)</sub> dove {F<sub>n</sub>} è la successione di Fibonacci
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Vedi giornalino 4, problema 25.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Start --><B><font color=blue>Problema:</font></B><!-- BBCode End --> 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:
<BR>p | F<sub>(p+1)/2</sub>. Così, per esempio: 13 | F<sub>7</sub> e 37 | F<sub>19</sub>.
<BR>
<BR>Ebbene, di quella che fino a ieri sera sembrava soltanto un\'ulteriore conferma della legge di Guy dei piccoli numeri oggi possiedo un <!-- BBCode Start --><I>proof</I><!-- BBCode End --> decisamente elementare, se non persino banale... Naturalmente, l\'invito è a provare il <!-- BBCode Start --><I>claim</I><!-- BBCode End -->.
<BR>
<BR>Buon divertimento e ciao,
<BR>--- S. Tr.
<BR>
<BR>
<BR>\"Un\'opera è completa soltanto quando l\'obiettivo è raggiunto.\" - Paulo Coelho, <!-- BBCode Start --><I>L\'Alchimista</I><!-- BBCode End --><font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 07-12-2004 14:09 ]

Bloccato