[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

Ciao. Sentite questo:
<BR>
<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>
<BR>EDIT: nella prima formulazione c\'era una stupidaggine piuttosto evidente. Per fortuna che nessuno se ne è accorto...
<BR>
<BR>Buon lavoro!
<BR>
<BR>M.
<BR>
<BR>[ Questo Messaggio è stato Modificato da: marco il 26-11-2004 08:05 ]<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 26-11-2004 08:05 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

sprmnt21
Messaggi: 559
Iscritto il: 01 gen 1970, 01:00

Messaggio da sprmnt21 » 01 gen 1970, 01:33

Do\' un piccolissimo contributo a semplificare (?) il problema.
<BR>
<BR>Per p>2, datp che p dispari, si ha che F(p-1)F(p+1)=Fp^2-1=(Fp-1)(Fp+1).Quindi la tesi da provare e\' equivalente (per p>2) a provare che
<BR>
<BR>p|(Fp-1)Fp(Fp+1).
<BR>
<BR>
<BR>
<BR>

sprmnt21
Messaggi: 559
Iscritto il: 01 gen 1970, 01:00

Messaggio da sprmnt21 » 01 gen 1970, 01:33

provo ad andare avanti.
<BR>
<BR>per p>2, la formula di Binet per i numeri di Fibonacci Fp, da\' un\'eguaglianza del tipo:
<BR>
<BR>2^(p-1)Fp = Cp1 + Cp3*5+Cp5*5^2 + ... +Cpp*5^((p-1)/2).
<BR>
<BR>Dato che Cpi == 0 (mod p) per i=/=p, Cpp==1 (mod p) e 2^(p-1)==1 (mod p), si ha che Fp == 5^((p-1)/2) (mod p) o Fp^2 == 5^(p-1) (mod p).
<BR>
<BR>
<BR>Un altro progresso (piu\' (ri)correzione <IMG SRC="images/forum/icons/icon_smile.gif"> )
<BR>
<BR>Cioe\' Fp^2 == {0, per p=5; 1, per p=/=5} (mod p).
<BR>
<BR>
<BR>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: sprmnt21 il 26-11-2004 13:17 ]<BR><BR>[ Questo Messaggio è stato Modificato da: sprmnt21 il 26-11-2004 13:27 ]

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>PREMESSE.</B><!-- BBCode End -->
<BR>
<BR>Mostrerò di seguito che, per ogni primo intero p > 0: p | F<sub>p - Leg(p,5)</sub>, ove Leg(p,5) è il simbolo di Legendre di numeratore p e denumeratore 5, rispondendo in tal modo in un sol colpo a due delle questioni poste dal nostro caro marco, e fra queste al <!-- BBCode Start --><I>bonus problem</I><!-- BBCode End -->. In quanto alla condizione di minimalità, be\'... mi pare proprio che i conti non tornino! Perché? Eh, fate un po\' voi: F<sub>7</sub> = 13, F<sub>11</sub> = 89, F<sub>13</sub> = 233 <!-- BBCode Start --><I>and so on going</I><!-- BBCode End -->... Ho impegnato l\'intera mattinata e tutte le mie energie nello sforzo di rendere <!-- BBCode Start --><I>attendibili</I><!-- BBCode End --> i miei argomenti! Ecco, <!-- BBCode Start --><I>a posteriori</I><!-- BBCode End -->, direi che n\'è valsa realmente la pena, e lo dico senz\'ombra di presunzione, ma piuttosto compiaciuto del mio <!-- BBCode Start --><I>lavoro</I><!-- BBCode End -->!!! Ok, ciò premesso, mettetevi comodi e cercate di seguirmi...
<BR>
<BR>P.S.: ho scelto di segmentare la soluzione onde soltanto migliorarne la leggibilità: a qualcuno sembrerà bislacco, ma ho letto un articolo in proposito giusto un paio di giorni fa...
<BR>
<BR>
<BR>\"C\'è un solo bene: il sapere. E un solo male: l\'ignoranza.\" - Socrate<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 26-11-2004 13:55 ]

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>ALGEBRA+.</B><!-- BBCode End -->
<BR>
<BR>Per ogni primo intero q > 2, sia S<sub>q</sub> := {a + b·sqrt(q): a, b € Z}. Evidentemente, S<sub>q</sub> è un sottoinsieme di R e un sovrainsieme degli interi. Inoltre, S<sub>q</sub> è algebri-
<BR>camente chiuso rispetto alla somma ordinaria ereditata dalla sovrastruttura dei reali e così nondimeno rispetto al prodotto <!-- BBCode Start --><I>standard</I><!-- BBCode End --> *: S<sub>q</sub> x S<sub>q</sub> --> S<sub>q</sub> definito assumendo, per ogni a, b, c, d € Z:
<BR>
<BR><center>[a + b·sqrt(q)] * [c + d·sqrt(5)] = (ac+q·bd) + (ad+bc)·sqrt(q)</center>
<BR>E\' (quasi) un esercizio di <!-- BBCode Start --><I>routine</I><!-- BBCode End --> verificare che (S<sub>q</sub>, +, *) è un anello commutativo unitario (l\'unità è l\'elemento e = 1), in cui vige la legge di annullamento del prodotto (dunque, un dominio di integrità), e che inoltre il più comune anello degli interi (Z, +, ·) è nulla più (beh, adesso...) che un sottoanello di (S<sub>q</sub>, +, *). Per ogni n € N<sub>0</sub> ed ogni x € S<sub>q</sub>, definiamo poi in modo naturale:
<BR>x<sup>n</sup> := x * x * ... * x, ove il prodotto coinvolge n fattori tutti eguali ad x. Per definizione, assumiamo quindi x<sup>0</sup> := 1.
<BR>
<BR>Be\', a questo punto, piccolo <!-- BBCode Start --><I>break</I><!-- BBCode End --> pubblicitario, ché debbo andare a <!-- BBCode Start --><I>calarmi la pasta</I><!-- BBCode End -->... A dopo per il resto!!!
<BR>
<BR>EDIT: rifiniture + integrazione + correzione.
<BR>
<BR>
<BR>\"Anelo all\'eternità perché lì troverò i miei quadri non dipinti e le poesie che ancora non ho scritto.\" - Kahlil Gibran<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-11-2004 15:21 ]

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-26 12:34, HiTLeuLeR wrote:
<BR>In quanto alla condizione di minimalità, be\'... mi pare proprio che i conti non tornino!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>...infatti la minimalità è scomparsa nottetempo. Mi ero molto stupito, stamane, di averla scampata...
[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, ecco... tutto nasce dal fatto ch\'io ho dato lettura al tuo quesito ieri sera, caro marco, attorno alle 22:00, quando ancora - debbo presumere - non avevi avuto occasione di apportare le dovute modifiche al \"testo incriminato\". Scopro soltanto adesso della tua correzione, tutto qui! Ero così concentrato sul problema che non ho pensato di verificare se avessi già \"rivisitato le tue scritture\"!!! Vabbe\', in fondo, non è successo nulla di grave, i malintesi sono sempre dietro l\'angolo, soprattutto quando... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>
<BR>\"Grazie a Dio, esiste il malinteso.\" - Charles Baudelaire<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 26-11-2004 14:02 ]

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>COME TI ESTENDO LA DIVISIONE...</B><!-- BBCode End -->
<BR>
<BR>L\'idea è adesso di estendere ad S<sub>q</sub> la nozione di divisibilità classicamente riferita agli interi di Z. Be\', molto banalmente, se m, n € S<sub>q</sub> ed n è diverso dallo zero, si dice che m è divisibile per n, ovvero che n divide m, o ancora che n è un divisore di m (in S<sub>q</sub>), e si scrive n | m, sse esiste un qualche k € S<sub>q</sub> tale che: m = n*k.
<BR>
<BR>Utilizzando il concetto di divisibilità appena qui sopra introdotto, possiamo dunque <!-- BBCode Start --><I>trasportare</I><!-- BBCode End --> in S<sub>q</sub> la relazione di congruenza modulare, assumendo (definizione) che, comunque scelti x, y, m € S<sub>q</sub>, con m diverso dallo zero, x è congruo ad y modulo m sse m | (x-y) in S<sub>q</sub>; nel qual caso, scriviamo: x =<sub>q</sub> y mod m.
<BR>
<BR>La relazione di congruenza mod m così stabilita fra gli elementi di S<sub>q</sub> è un\'equivalenza, e soddisfa inoltre alcune peculiari proprietà, del tutto analoghe a quelle delle più ordinarie congruenze sugli interi di Z. Fra queste:
<BR>
<BR>i) p.o. a, b, c, d € S<sub>q</sub>: a =<sub>q</sub> b mod m & c =<sub>q</sub> d mod m ==> a+c =<sub>q</sub> b+d mod m;
<BR>ii) p.o. a, b, c € S<sub>q</sub>, con c =\\= 0: a =<sub>q</sub> b mod m ==> a*c =<sub>q</sub> b*c mod m*c;
<BR>iii) se n € S<sub>q</sub> ed n | m, allora: a =<sub>q</sub> b mod m ==> a =<sub>q</sub> b mod n, p.o. a, b € S<sub>q</sub>;
<BR>iv) comunque scelti a, b, c € S<sub>q</sub>: a =<sub>q</sub> b mod m ==> a*c =<sub>q</sub> b*c mod m;
<BR>v) per ogni a, b, c, d € S<sub>q</sub>: a*c =<sub>q</sub> b*d mod m;
<BR>vi) per qualsiasi k € N ed ogni a, b € S<sub>q</sub>: a =<sub>q</sub> b mod m ==> a<sup>k</sup> =<sub>q</sub> b<sup>k</sup> mod m.
<BR>
<BR>Ultima, ma non ultima, vale l\'interessante implicazione (<!-- BBCode Start --><B>proprietà (H.1)</B><!-- BBCode End -->) secondo cui, se x, y, m € Z ed m è diverso dallo zero, allora: x =<sub>q</sub> y mod m sse x = y mod m. Si ricordi, in tal senso, quanto detto in principio riguardo al fatto che (Z, +, ·) è un sottoanello di (S<sub>q</sub>, +, *). Ok, mostriamo che la condizione è necessaria (l\'inversa è a dir poco banale). Secondo definizione: x = y mod m sse esiste un k € S<sub>q</sub> tale che: x - y = mk. E tuttavia: S<sub>q</sub> := {a + b·sqrt(q): a, b € Z}, sicché - in ultima analisi: x = y mod m sse esistono interi a, b € Z per i quali:
<BR>x - y = m·[a + b·sqrt(q)]. Ora, se b fosse diverso dallo zero, se ne avrebbe presto a dedurre che: sqrt(q) = [(x - y)/m - a]/b, con x, y, a, b, m € Z, in evidente contraddizione col fatto che sqrt(q) è un numero irrazionale. Necessariamente, quindi: b = 0, cosicché: k € Z, e di qui l\'asserto, q.e.d.
<BR>
<BR>EDIT: non riuscivo a incollare il resto della soluzione, arrrgh!!! Ultimamente, il <!-- BBCode Start --><I>server</I><!-- BBCode End --> fa parecchio i capricci... gli ci vorrebbe una bella dose di bastonate!!! Sììì, so cosa state pensando: \"Anche a te!!!\" Gnegne, antipatici... <IMG SRC="images/forum/icons/icon_mad.gif">
<BR>
<BR>
<BR>\"Ci sono anime schiave che spingono la riconoscenza per i benefici ricevuti al punto da strangolare se stesse col laccio della gratitudine.\" - F. W. Nietzsche <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 26-11-2004 18:54 ]

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>IL TEOREMA DI HITLEULER-FERMAT.</B><!-- BBCode End --> <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>Sì, sono d\'accordo anch\'io: che sboroooooone, puaaah... Eppure, non suonerebbe affatto male, caspiterina... Vabbe\', <!-- BBCode Start --><I>ciancio alle bande</I><!-- BBCode End --> e entriamo nel vivo della soluzione!!! Nel seguito, salvo che non sia altrimenti specificato, tutte le congruenze indicate s\'intendono condotte in S<sub>q</sub>.
<BR>
<BR>NOTA: qui come altrove, si pone implicitamente: q<sup>p/2</sup> := [sqrt(q)]<sup>p</sup>.
<BR>
<BR><!-- BBCode Start --><B>Lemma di HiT:</B><!-- BBCode End --> per ogni primo intero p > 2: q<sup>p/2</sup> =<sub>q</sub> Leg(p,q)·sqrt(q) mod p.
<BR>
<BR>Dim.: come noto, se p è un primo intero > 2, necessariamente: p = 1 mod 2. E allora: q<sup>p/2</sup> =<sub>q</sub> Leg(p,q)·sqrt(q) mod p se e soltanto se esiste k € S<sub>q</sub> tale che: p*k = q<sup>p/2</sup> - Leg(p,q)·sqrt(q) = sqrt(q) · [q<sup>(p-1)/2</sup> - Leg(p,q)]. Del resto, essendo p un primo intero positivo dispari, per coerenza con il lemma di Eulero, risulta che: q<sup>(p-1)/2</sup> = Leg(p,q) mod p, perciocché è determinato un m € N<sub>0</sub> per il quale: q<sup>(p-1)/2</sup> - Leg(p,q) = mp. Di qui la tesi, pur di assumere k := m·sqrt(q), q.e.d.
<BR>
<BR><!-- BBCode Start --><B>Teorema di HiTLeuLeR-FeRMaT:</B><!-- BBCode End --> per ogni a, b € Z ed ogni primo intero p > 2: [a+b·sqrt(q)]<sup>p</sup> =<sub>q</sub> a + b·sqrt(q)·Leg(p,q) mod p.
<BR>
<BR>Dim.: com\'è nei miei <!-- BBCode Start --><I>standard</I><!-- BBCode End --> di scrittura, sia Bin(a,b) il coefficiente binomiale di ordine a su b, per ogni a € N ed ogni b = 0, 1, ..., a. E allora, come noto: Bin(p,k) = 0 mod p, per ogni k = 1, 2, ..., p-1, e perciò - stante la proprietà (H.1) delle congruenze in S<sub>q</sub>: Bin(p,k) =<sub>q</sub> 0 mod p. <!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, passando per il teorema del binomiale di Isacco Newton (Dio vi salvi dai fisici prima che dagli <!-- BBCode Start --><I>ingenieri</I><!-- BBCode End -->...):
<BR>
<BR>[a+b·sqrt(q)]<sup>p</sup> =<sub>q</sub> a<sup>p</sup> + sum<sub>k=1...p-1</sub> Bin(p,k) · a<sup>p-k</sup> · b<sup>k</sup> · q<sup>k/2</sup> + b<sup>p</sup> · q<sup>p/2</sup> =<sub>q</sub>
<BR><font color=white>[a+b·sqrt(q)]<sup>p</sup> </font>=<sub>q</sub> a<sup>p</sup> + b<sup>p</sup> · q<sup>p/2</sup> + 0 =<sub>q</sub> a<sup>p</sup> + b<sup>p</sup> · q<sup>p/2</sup> mod p.
<BR>
<BR>D\'altro canto, coerentemente con il piccolo teorema di Fermat, riferito agli interi ordinari di Z: a<sup>p</sup> = a mod p e b<sup>p</sup> = b mod p, cosicché - ancora in virtù della proprietà (H.1): a<sup>p</sup> =<sub>q</sub> a mod p e b<sup>p</sup> =<sub>q</sub> b mod p. Inoltre, per il lemma di HiT:
<BR>q<sup>p/2</sup> =<sub>q</sub> Leg(p,q)·sqrt(q) mod p, e perciò - in definitiva:
<BR>
<BR>[a+b·sqrt(q)]<sup>p</sup> =<sub>q</sub> a<sup>p</sup> + b<sup>p</sup> · q<sup>p/2</sup> =<sub>q</sub> a + b · sqrt(q) · Leg(p,q) mod p, q.e.d. <IMG SRC="images/forum/icons/icon21.gif">
<BR>
<BR>
<BR>\"L\'uomo di poco sapere invecchia come un bove. Crescono le sue carni, ma non cresce la sua saggezza.\" - Buddha<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-11-2004 15:24 ]

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>LA SOLUZIONE DEL PROBLEMA.</B><!-- BBCode End -->
<BR>
<BR>Come anticipato già nelle premesse, intendo innanzitutto dimostrare che, per ogni primo intero p > 0: p | F<sub>p - Leg(p,5)</sub>, ove la condizione di divisibilità s\'intende riferita, qui come nel seguito, all\'anello ordinario degli interi. Per il lemma di Gauss sul carattere quadratico di 2: Leg(2,5) = (-1)^[(5<sup>2</sup> - 1)/8] = (-1)<sup>3</sup> = -1, sicché: [p - Leg(p,5)]<sub>p=2</sub> = 3, e in effetti: 2 | F<sub>3</sub>, poiché: F<sub>3</sub> = 2. Analogamente: Leg(5,5) = 0. Così: [p - Leg(p,5)]<sub>p=5</sub> = 5, e ancora: 5 | F<sub>5</sub>, dacché: F<sub>5</sub> = 5.
<BR>
<BR>Ciò stabilito, sia dunque p un primo intero > 2 e diverso da 5. In tal caso, <!-- BBCode Start --><I>sic et simpliciter</I><!-- BBCode End -->: Leg(p,5) = 1 <!-- BBCode Start --><I>aut</I><!-- BBCode End --> Leg(p,5) = -1, a secondo che p risulti o meno un residuo quadratico mod 5. Procediamo distinguendo i due casi:
<BR>
<BR>1° caso) p non è residuo quadratico mod 5, ovvero: Leg(p,5) = -1. E allora:
<BR>p - Leg(p,5) = p + 1, e si tratta perciò di mostrare che: p | F<sub>p+1</sub>. 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> = sqrt(5) * ([1+sqrt(5)]<sup>n</sup> - [1-sqrt(5)]<sup>n</sup>). <!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, per applicazone del teorema di HiTLeuLeR-FeRMaT (uhauhauha, che megalomane, gh...):
<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<sup>p</sup></font>=<sub>5</sub> sqrt(5) * ([1+sqrt(5)]*[1-sqrt(5)] - [1-sqrt(5)]*[1+sqrt(5)]) =<sub>5</sub> 0 mod p
<BR>
<BR>Tuttavia, a primo e ultimo membro della relazione modulare così ottenuta figurano degli interi di Z, così da potersi dedurre - in virtù della proprietà (H.1) - che: 2<sup>p+1</sup> · 5F<sub>p+1</sub> = 0 mod p, ovvero: 10F<sub>p+1</sub> = 0 mod p. Di qui, considerando che p è primo con 10 e sfruttando di conseguenza il 2° teorema di Euclide dell\'Aritmetica, si conclude finalmente che: F<sub>p+1</sub> = 0 mod p, ossia: p | F<sub>p+1</sub>.
<BR>
<BR>2° caso) p è residuo quadratico mod 5, cioè a dirsi: Leg(p,5) = 1. E allora:
<BR>p - Leg(p,5) = p - 1, e tutto si riduce a provare che: p | F<sub>p-1</sub>. Ancora per la formula di Binet: 2<sup>p-1</sup> · 5F<sub>p-1</sub> = [1+sqrt(5)]<sup>p-1</sup> - [1-sqrt(5)]<sup>p-1</sup>; sicché, moltiplicando<sup>(1)</sup> primo e secondo membro per [1+sqrt(5)]*[1-sqrt(5)] = -4, si deriva che: -2<sup>p+1</sup> · 5F<sub>p-1</sub> = sqrt(5) * ([1-sqrt(5)] * [1+sqrt(5)]<sup>p</sup> - [1+sqrt(5)] * [1-sqrt(5)]<sup>p</sup>). E così, stante il mirabilissimo (...) 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<sup>p</sup></font>=<sub>5</sub> sqrt(5) * ([1-sqrt(5)]*[1+sqrt(5)] - [1+sqrt(5)]*[1-sqrt(5)]) =<sub>5</sub> 0 mod p.
<BR>
<BR>Orbene, a primo ed ultimo membro della catena di congruenze così ottenuta figurano degli interi ordinari, cosicché - vista l\'ormai inflazionata proprietà (H.1):
<BR>-2<sup>p+1</sup> · 5F<sub>p-1</sub> = 0 mod p, ovvero: 10F<sub>p-1</sub> = 0 mod p. Di qui, osservando che p è primo con 10 e applicando a seguire il 2° teorema di Euclide dell\'Aritmetica, si trae alfine che: F<sub>p-1</sub> = 0 mod p, ovvero: p | F<sub>p-1</sub>, q.e.d.
<BR>
<BR><sup>(1)</sup>: il riferimento è al prodotto non-<!-- BBCode Start --><I>standard</I><!-- BBCode End --> di S<sub>5</sub>.
<BR>
<BR>EDIT: inserita la radice mancante!!!
<BR>
<BR>
<BR>\"Quando nel mondo appare un vero genio, lo si riconosce dal fatto che tutti gli idioti fanno banda contro di lui.\" - Jonathan Swift<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 01-12-2004 22: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>CONCLUSIONI</B><!-- BBCode End -->.
<BR>
<BR>Osserviamo che, per ogni primo intero q > 0: Leg(q,5) = Leg(b,5), ove b rappresenta la cifra meno significativa nella rappresentazione decimale di q. Ora, siccome <!-- BBCode Start --><I>tutti</I><!-- BBCode End --> i primi interi > 2 terminano per una cifra (decimale) dispari, e dacché: Leg(1,5) = Leg(-1,5) = 1 e Leg(2,5) = Leg(3,5) = Leg(7,5) = -1, è lecito concludere - mettendo insieme quanto sinora stabilito - che, essendo p un primo naturale qualsivoglia: a) p | F<sub>p-1</sub> se la cifra meno significativa della rappresenta-
<BR>zione decimale di p è 1 <!-- BBCode Start --><I>vel</I><!-- BBCode End --> 9; b) p | F<sub>p</sub> se p = 5; c) p | F<sub>p+1</sub> se p = 2 oppure se la cifra meno significativa della rappresentazione decimale di p è 3 <!-- BBCode Start --><I>vel</I><!-- BBCode End --> 7. E in effetti, è banalissimo dimostare che le condizioni a)-c) appena elencate, oltre che sufficienti, sono pure necessarie. Basta combinare le precedenti alla proprietà per cui: gcd(F<sub>n</sub>, F<sub>n+1</sub>) = 1, per ogni n € N.
<BR>
<BR>Bene, penso di aver detto molto più di quel che avrei dovuto! Perciò, se fossi in me, a questo punto, mi fermerei qui!!! Maaa...
<BR>
<BR>
<BR>\"Nessuno ha mai commesso un errore più grande di colui che non ha fatto nulla soltanto perché poteva fare troppo poco.\" - Edmund Burke<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 26-11-2004 17:53 ]

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

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

[mode <!-- BBCode Start --><I>invettiva</I><!-- BBCode End --> ON]
<BR>
<BR>...ma ciò nonostante, sento di dover aggiungere ancora una piccola postilla, a tutto questo! Dunque, siccome il problema è stato classificato da marco come un [N+], mi sono permesso (naaah, non tenterò di nasconderlo, tranquilli...) qualche timida divagazione su <!-- BBCode Start --><I>topic</I><!-- BBCode End --> poco allineati agli standard di questo forum (che io <!-- BBCode Start --><I>adoro</I><!-- BBCode End -->, se mai non fosse stato chiaro)!!!
<BR>
<BR>Del resto, in giro per il <!-- BBCode Start --><I>web</I><!-- BBCode End -->, non è raro apprendere di IMO-<!-- BBCode Start --><I>boys</I><!-- BBCode End --> capaci di maneggiare con disinvoltura curve ellittiche e forme modulari: penso soprattutto ai campioni magiari!!! E non sarà di certo un caso se l\'Ungheria è - almeno per quanto mi risulta - uno fra gli IMO-paesi più forti nel mondo, non vi pare? Ecco, forse questo dovrebbe far riflettere un po\' tutti, e particolarmente quanti ancora si ostinano a ritenere che la Matematica e la sua pur nobile cugina olimpica debbano per lo più evitare d\'incrociar le proprie strade...
<BR>
<BR>[mode <!-- BBCode Start --><I>invettiva</I><!-- BBCode End --> OFF]
<BR>
<BR>
<BR>\"Tutti desiderano possedere la conoscenza, ma relativamente pochi sono disposti a pagarne il prezzo.\" - Giovenale

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

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Vabbe\', siccome marco tarda a rispondere, ché avrà pure diritto a una sua vita privata, approfitto del suo <!-- BBCode Start --><I>thread</I><!-- BBCode End --> per rilanciare con un altro problema pertinente i Fibonacci - per quel che mi è noto, assolutamente originale!!! Ringrazio lo stesso marco per avermi dato l\'<!-- BBCode Start --><I>occasione</I><!-- BBCode End --> di pensarci su...
<BR>
<BR><font color=red><!-- BBCode Start --><B>HiT\'s problem</B><!-- BBCode End --></font>: siano {F<sub>n</sub>: n € N} la sequenza dei Fibonacci e {p<sub>n</sub>: n € N<sub>0</sub>} la successione ordinatamente crescente di tutti e soli i numeri primi naturali:
<BR>p<sub>1</sub> = 2, p<sub>2</sub> = 3, p<sub>3</sub> = 5, p<sub>4</sub> = 7 e così via all\'infinito (già, il teorema di Euclide)!
<BR>
<BR>Ebbene, si dimostri che esistono infiniti k € N<sub>0</sub> tali che, per ogni n € N<sub>0</sub>, F<sub>p<sub>n</sub></sub> non sia divisibile per p<sub>k</sub>. <IMG SRC="images/forum/icons/icon24.gif">
<BR>
<BR>
<BR>\"I numeri sono come le persone: torturali abbastanza e ti diranno qualsiasi cosa.\" - <!-- BBCode Start --><I>S. Tr.\'s philosophy</I><!-- BBCode End --><font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 01-12-2004 22:45 ]

fph
Site Admin
Messaggi: 3861
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 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-26 17:55, HiTLeuLeR wrote:
<BR>[mode <!-- BBCode Start --><I>invettiva</I><!-- BBCode End --> ON]
<BR>...ma ciò nonostante, sento di dover aggiungere ancora una piccola postilla, a tutto questo! Dunque, siccome il problema è stato classificato da marco come un [N+], mi sono permesso (naaah, non tenterò di nasconderlo, tranquilli...) qualche timida divagazione su <!-- BBCode Start --><I>topic</I><!-- BBCode End --> poco allineati agli standard di questo forum (che io <!-- BBCode Start --><I>adoro</I><!-- BBCode End -->, se mai non fosse stato chiaro)!!!
<BR>
<BR>Del resto, in giro per il <!-- BBCode Start --><I>web</I><!-- BBCode End -->, non è raro apprendere di IMO-<!-- BBCode Start --><I>boys</I><!-- BBCode End --> capaci di maneggiare con disinvoltura curve ellittiche e forme modulari: penso soprattutto ai campioni magiari!!! E non sarà di certo un caso se l\'Ungheria è - almeno per quanto mi risulta - uno fra gli IMO-paesi più forti nel mondo, non vi pare? Ecco, forse questo dovrebbe far riflettere un po\' tutti, e particolarmente quanti ancora si ostinano a ritenere che la Matematica e la sua pur nobile cugina olimpica debbano per lo più evitare d\'incrociar le proprie strade...
<BR>[mode <!-- BBCode Start --><I>invettiva</I><!-- BBCode End --> OFF]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Non ho capito il riferimento all\'Ungheria. Me lo puoi spiegare? Comunque i quesiti delle IMO si possono risolvere /anche/ (di preferenza, ma comunque non /soltanto/) con metodi totalmente elementari perche\' questa e\' una politica specifica del comitato organizzatore, non e\' nulla che abbiamo deciso noi.
<BR>
<BR>Forse Ungheria e Corea fanno stage in cui spiegano le curve ellittiche, non lo escludo. Vista la situazione attuale pero\' qui in Italia non abbiamo tempo, negli stage, di preparare adeguatamente i ragazzi neanche sui topic piu\' elementari (e qui ricadiamo nel discorso su \"come mai l\'Italia e\' scarsa alle IMO\" che e\' gia\' stato fatto molte volte...)
<BR>
<BR>ciao,
<BR>--f
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

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

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Hp) Divagare sulla Matematica giova agli olimpionici.
<BR>
<BR>Ts) Come del resto più volte suggerito e da più parti, si dovrebbe dedicare maggior spazio, anche qui sul forum, alla Matematica non propriamente olimpica, e non stigmatizzare certi problemi o le loro soluzioni<sup>(1)</sup>.
<BR>
<BR>--------------
<BR>
<BR>Forse così il senso sarà più chiaro! Non avevo alcuna intenzione di polemizzare circa i contenuti degli IMO-<!-- BBCode Start --><I>problems</I><!-- BBCode End -->, anzi... non avevo alcuna intenzione di polemizzare, in verità!!! Questa è una precisazione dovuta, non tanto per quel che già è stato scritto o è stato detto, ma piuttosto per quel che ancora ha da venire, se mai a questo mio sproloquire si darà un seguito...
<BR>
<BR>Ora, per quanto possa essere irrilevante la mia opinione in proposito, trovo assolutamente azzeccata l\'impronta su cui sono informati gli esercizi delle gare nazionali e internazionali, non ho mai inteso sostenere il contrario, e le tue precisazioni in merito, ancorché istruttive, consentimi di dirlo, mi sono parse piuttosto fuori luogo, come del resto saranno parse a te le mie riflessioni, non è ch\'io nutra dubbi a riguardo... Ecco, probabilmente mi avrai miscompreso, o più probabilmente mi sarò lasciato miscomprendere, o <!-- BBCode Start --><I>maybe</I><!-- BBCode End --> son io ad aver frainteso il senso delle tue parole, ma tant\'è...
<BR>
<BR>Neppure per un istante, credimi, mi è balenata per la testa l\'idea che il Calcolo e la Teoria di Galois dovessero o potessero in qualche modo rientrare fra gli argomenti da olimpiade: ci mancherebbe altro!!! Il mio era piuttosto un discorso di formazione del pensiero Matematico, tutto lì. Forse, e dico <!-- BBCode Start --><I>forse</I><!-- BBCode End --> solo per non sembrare più presuntuoso di quanto già non sia, dare spazio alla Matematica ultra-olimpica, senza tuttavia che questo voglia significare perdere di vista le finalità del forum e il senso ultimo dell\'iniziativa olimpica, potrebbe affinare la <!-- BBCode Start --><I>forma mentis</I><!-- BBCode End --> dei nostri campioni<sup>(2)</sup> e dar loro quello slancio in più per affrontare, nei termini <!-- BBCode Start --><I>elementari</I><!-- BBCode End --> propri di ogni buona soluzione \"IMO-<!-- BBCode Start --><I>style</I><!-- BBCode End -->\", la sfida con gli altri paesi concorrenti! Già, ché forse una percezione più concreta dell\'aspetto agonistico delle gare (inutile fare gli ipocriti, suvvia, anche questo fa parte del sistema) potrebbe - alla lunga - dare i suoi bei frutti...
<BR>
<BR>Ciao,
<BR>S. Tr.
<BR>
<BR>------
<BR>
<BR><sup>(1)</sup>: btw, non mi riferisco a nessun caso in particolare.
<BR>
<BR><sup>(2)</sup>: sì, in parte li sento anche miei, e penso che non sia un delitto, in fondo in fondo... Qualcuno lo chiamerebbe \"orgoglio nazionale\", ed io - almeno dal punto di vista scientifico e secolare - sono molto <!-- BBCode Start --><I>orgoglione</I><!-- BBCode End --> dell\'Italia, e non ho riserve nel confessarlo! Dell\'altra italia, be\'... preferisco non parlare!!!
<BR>
<BR>
<BR>\"La noia nacque un giorno dall\'uniformità del pensiero.\" - Antoine La Motte Houdar<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 27-11-2004 13:47 ]

Bloccato