[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

Scusatemi per l\'assenza. Non ho ancora avuto tempo di studiare il trattato di Hit, ma lo farò quanto prima.
<BR>
<BR>Ho classificato il problema [N+] perché quando l\'ho postato avevo in mente solo una soluzione che sfruttava in modo sostanziale i campi finiti (e, ad occhio, dovrebbe essere +/- sul filone dello scritto di Hit). Siccome i campi finiti sono definitely fuori dal syllabus olimpico, ho scritto [N+] [btw.: come avrete capito, anch\'io adoro la Teoria dei Numeri di un certo livello].
<BR>
<BR>Tuttavia, in questo w.e. di ponzate, ho trovato una soluzione decisamente più semplice, radicalmente diversa, che sfrutta alcune idee dell\'algebra lineare, e di gran lunga assolutemente più abbordabile con gli strumenti cosiddetti \"olimpici\". In tal caso, il problema si classificherebbe come [N] (sebbene di livello di difficoltà decisamente alto). Appena ho tempo le posto entrambe, così le vediamo e le possiamo commentare insieme.
<BR>
<BR>La mia opinione sulla matematica non-olimpica è: secondo me va bene, in questo Forum. A patto che sia CHIARAMENTE contrassegnata come tale
<BR>(e, possibilimente, sia in qualche modo funzionale alle olimpiadi).
<BR>
<BR>E\' inutile scoraggiare un aspirante IMO-boy [anzi: Cese-boy] con problemi apparentemente innocui ma che richiedono tensori, spazi vettoriali, fibrati tangenti e gruppi di omologia. Tuttavia, se qualche volenteroso le vuole studiare qui a suo rischio e pericolo, perché no?
<BR>
<BR>Voglio dire: c\'è una zona del Forum dove la gente sta diveretendosi a proporre rompicapi (v. il Pensiero Laterale). Che male c\'è se qualcun\'altro vuole divertirsi con rompicapi da quarto anno di Matematica? Basta che lo dichiari... Se qualcuno mi chiede di dimostrare che cosa fa un certo limite, gli sputo in un occhio, ma altri la pensano diversamente. Come penso ci sia tanta gente a cui la Teoria dei Numeri Algebrici fa schifo...
<BR>
<BR>Alla prox.
<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
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

Ciao.
<BR>
<BR>Ho studiato il testo. Allora:
<BR>
<BR>@sprmnt: Mi sembra che ai tuoi commenti manchi veramente un epsilon per risolvere il problema base. O mi sbaglio?
<BR>
<BR>@Hit: quasi tutto giusto. Il problema più grosso è che c\'è qualcosa che non torna nella def. di S<sub>5</sub>. Così come l\'hai detta tu, succede la cosa strana che sqrt(5) al quadrato NON fa 5. E questo è un guaio, dato che lo sfrutti pesantemente per dimostrare il Lemma di HiT.
<BR>
<BR>Comunque, cambiando un - in un +, si torna alla definizione solita, in cui radice di 5 al quadrato fa proprio 5. Torna tutto, tranne alla fine dove dici che (1-r5)(1+r5) = 6. In verità con la nuova definizione fa -4. Il resto del ragionamento continua a funzionare (e, anzi, ti è sparito quel fastidioso fattore 3: 3 è un primo normalissimo, mentre i casi \"strani\" sono 2 e 5. Mi chiedevo come mai lo dimostrassi esplicitamente...).
<BR>
<BR>Quanto prima le mie dimostrazioni (sempreché vi interessino...)
<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."

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

Messaggio da sprmnt21 » 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 13:08, marco wrote:
<BR>Ciao.
<BR>
<BR>Ho studiato il testo. Allora:
<BR>
<BR>@sprmnt: Mi sembra che ai tuoi commenti manchi veramente un epsilon per risolvere il problema base. O mi sbaglio?
<BR>
<BR>M.[addsig]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>
<BR>Si. volendo dare solo le lineee principali del ragionamento, ritenevo il tutto chiuso, senza dare esplicitamente le conclusioni.
<BR>
<BR>Mi sembra che quanto indicato possa essere utilizzato per rispondere anche alla richiesta di \"caratterizzazione\": provero\' ad esplicitare.
<BR>
<BR>
<BR>

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 13:08, marco wrote:
<BR>Ho studiato il testo. Allora:
<BR>@Hit: quasi tutto giusto. Il problema più grosso è che c\'è qualcosa che non torna nella def. di S<sub>5</sub>. Così come l\'hai detta tu, succede la cosa strana che sqrt(5) al quadrato NON fa 5. E questo è un guaio, dato che lo sfrutti pesantemente per dimostrare il Lemma di HiT.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Mmmh... davvero non capisco a cosa tu ti riferisca, marco! Chiarisco innanzitutto che ho scelto di utilizzare un prodotto non-<!-- BBCode Start --><I>stardard</I><!-- BBCode End -->, piuttosto che il prodotto ordinario sui reali, per una ragione che dovrebbe apparire piuttosto evidente a chiunque abbia sentito mai parlare degli interi di Gauss... Ciò detto, ti inviterei ad essere più specifico, e definire più precisamente l\'errore che avresti ravvisato ne\' miei argomenti dimostrativi. Resterò in linea sperando di ricevere tuoi lumi!!!
<BR>
<BR>Ciao.
<BR>-- Salvo Tr.
<BR>
<BR>
<BR>\"Il cuoco copre i propri errori con la maionese, l\'avvocato con le parole, il medico con la terra...\" - W. Allen<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-11-2004 14:09 ]

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 13:08, marco wrote:
<BR>[...] 3 è un primo normalissimo, mentre i casi \"strani\" sono 2 e 5. Mi chiedevo come mai lo dimostrassi esplicitamente... [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ti rispondo quotando me stesso...
<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-26 17:19, HiTLeuLeR wrote:
<BR>2° caso) p è residuo quadratico mod 5, cioè a dirsi: Leg(p,5) = 1. E allora [...]: 30F<sub>p-1</sub> = 0 mod p. Di qui, osservando che <!-- BBCode Start --><B>p è primo con 30</B><!-- BBCode End --> e applicando a seguire il 2° teorema di Euclide dell\'Aritmetica, si trae alfine che: F<sub>p-1</sub> = 0 mod p.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>
<BR>\"Sono piuttosto confuso...\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon_eek.gif">

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 16:39, HiTLeuLeR wrote:
<BR><!-- BBCode Start --><B>IL TEOREMA DI HITLEULER-FERMAT.</B><!-- BBCode End --> <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<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.: [...]
<BR> q<sup>p/2</sup> - Leg(p,q)·sqrt(q) = sqrt(q) · [q<sup>(p-1)/2</sup> - Leg(p,q)][...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>In questo passaggio preciso usi il fatto che q<sup>1/2</sup> = sqrt(q). Ma non lo hai dimostrato da nessuna parte. [anzi, a dirla tutta, non hai ben definito nemmeno q<sup>p/2</sup>, ma transeat...].
<BR>
<BR>Se però ti attieni al tuo prodotto non standard *, sqrt(q)*sqrt(q) = -q. Mi sembra che hai preso l\'anello sbagliato: Z[sqrt(-q)], laddove ti sarebbe servito Z[sqrt(q)]; da questo bisognerebbe ridefinire la norma e il fatto che gli invertibili non sono più solo +/-1 e altre amenità, che però non usi nella dimo.
<BR>
<BR>Se invece intendevi proprio Z[sqrt(-5)], allora non hai più la formula di Binet a tua disposizione...
<BR>
<BR>Ma comunque, se cambi il prodotto * mettendo la relazione ovvia sqrt(5)*sqrt(5) = 5, tutto torna (con -4 al posto di 6 dove ho detto...[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

Ok, adesso ho finalmente capito cosa intendi!?! Sottile, davvero molto sottile... parlo di te! Provvedo subito a fissare il <!-- BBCode Start --><I>baco</I><!-- BBCode End -->... Ciao!!!
<BR>
<BR>EDIT: a questo punto, effettivamente, come già tu osservavi, l\'analisi preliminare del caso p = 3 diviene superflua! Ingenuamente, avevo in effetti trascurato di considerare con la dovuta attenzione come fosse definita la potenza q<sup>p/2</sup> nel prodotto non-<!-- BBCode Start --><I>standard</I><!-- BBCode End --> introdotto nella mia versione precedente della soluzione.
<BR>
<BR>
<BR>\"L\'aritmetica ha un grande potere nell\'elevare la mente costringendola a ragionare intorno a numeri astratti.\" - Platone<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-11-2004 15:35 ]

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

Messaggio da sprmnt21 » 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 13:32, sprmnt21 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-29 13:08, marco wrote:
<BR>Ciao.
<BR>
<BR>Ho studiato il testo. Allora:
<BR>
<BR>@sprmnt: Mi sembra che ai tuoi commenti manchi veramente un epsilon per risolvere il problema base. O mi sbaglio?
<BR>
<BR>M.[addsig]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>
<BR>Si. volendo dare solo le lineee principali del ragionamento, ritenevo il tutto chiuso, senza dare esplicitamente le conclusioni.
<BR>
<BR>Mi sembra che quanto indicato possa essere utilizzato per rispondere anche alla richiesta di \"caratterizzazione\": provero\' ad esplicitare.
<BR>
<BR>
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>
<BR>ritiro, le ultime (presuntuose) affermazioni!
<BR>
<BR>l\'idea (ingenua!?) era di proseguire, partendo da Fp^2== 1 (mod p) con Fp==+/-1 (mod p) per p=/=5.
<BR>
<BR>ma forse qui entrano in gioco questioni di residui quadratici o similia e in queste cose non mi ci addentro per nulla.
<BR>
<BR>Senza capirci granche\', cercando sul sito wolfram ho trovato che il simbolo di Legendre
<BR>
<BR>(5|p) ={1 per p==1,9; -1==3,7}(mod 10)
<BR>
<BR>che potrebbe azzeccarci con la seconda parte del problema.
<BR>
<BR>
<BR>
<BR>
<BR>
<BR>

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-29 16:10, sprmnt21 wrote:
<BR>(5|p) ={1 per p==1,9; -1==3,7}(mod 10)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì. Tutto vero. Ma temo che ti sei perso un precedente messaggio di Hit (quello intitolato CONCLUSIONI), perché la stessa osservazione l\'aveva già scritta lui.
<BR>
<BR>-----------------------
<BR>
<BR>Avevo promesso anche le mie dimostrazioni.
<BR>
<BR>Comincio con la prima:
<BR>
<BR>Il caso p=5 è singolare. Si fa il conto e si vede che vale (ii).
<BR>
<BR>Fisso ora p.
<BR>Supponiamo che f(x) = x<sup>2</sup> - x - 1 abbia due radici distinte. [è proprio qui, che 5 si rivela singolare: se p=5, f(x) è un quadrato perfetto...].
<BR>
<BR>Chiamo le due radici phi e phi*. Si vede subito che phi + phi* = 1 e phi.phi* = -1 [dai coefficienti di f(x)] e phi<sup>2</sup> = phi + 1.
<BR>
<BR>Definisco r5 := phi - phi*. Dato che le radici sono distinte, r5 è diverso da 0. Un conticino mostra che r5<sup>2</sup> = 5.
<BR>
<BR>Fissati questi, allora vale (mod. p) la seguente formula \"a-là-Binet\":
<BR>
<BR>F<sub>n</sub> = (r5)<sup>-1</sup> [ phi<sup>n</sup> - phi*<sup>n</sup> ]. [dim. per induzione].
<BR>
<BR>[non ho ancora -volutamente- specificato dove avvengono tutte queste somme e differenze. Diciamo che mi trovo in un campo opportuno...]
<BR>
<BR>A questo punto ci sono due casi:
<BR>
<BR>Caso (i\')
<BR>---------
<BR>
<BR>phi e phi* abitano negli interi mod p; in altri termini, f(x) = (x-phi)(x-phi*) mod.p.
<BR>
<BR>r5 [ = phi - phi*] è un intero mod.p. Questo implica che 5 è res.quadratico.
<BR>
<BR>La formula di Binet ha adesso perfettamente senso negli interi mod.p.
<BR>
<BR>A questo punto, applico il Teorema di Euler (quell\'altro, quello morto)
<BR>
<BR>F<sub>p-1</sub> = (r5)<sup>-1</sup> [ phi<sup>p-1</sup> - phi*<sup>p-1</sup> ] = (r5)<sup>-1</sup> [1 - 1] = 0. Quindi vale il caso (i).
<BR>
<BR>Caso (iii\')
<BR>-----------
<BR>
<BR>f(x) non si fattorizza mod.p. Allora i polinomi a coefficienti mod.p, modulo f(x), formano un -ta-daaaah- campo finito con p<sup>2</sup> elementi. Qui è ovvio trovare phi e phi*: phi = x e phi* = 1 - x.
<BR>
<BR>Se p=2 siamo in questo caso (iii\') [verifica diretta]. Se invece p diverso da 2 e cinque, dato che r5 = 2 phi - 1, 5 non può essere res.quadratico.
<BR>
<BR>Ho trovato un campo che contiene phi e phi* distinti. [per chi conosce gli interi di Gauss: sto facendo la stessa operazione di estensione degli interi, solo che non parto da Z, ma da Z mod. p.]. Quindi anche qui posso trovare la formula di Binet, solo che stavolta ha significato nel campo con p<sup>2</sup> elementi.
<BR>
<BR>Gli unici fatti che mi servono sui questo campo finito sono i seguenti:
<BR>
<BR>-per ogni a non nullo, vale a<sup>p^2-1</sup> = 1 [l\'analogo del Teorema di Euler, quello morto]
<BR>
<BR>-dato a non nullo, a<sup>p-1</sup> = 1 sse a appartiene agli interi mod.p [implicazione inversa del T.E.q.m.]
<BR>
<BR>-esiste una funzione \'*\' (il coniugio) bigettiva del campo in sé, che rispetta somme e prodotti (isomorfismo di campo) e t.c. per gli interi mod.p vale a = a*. Questa funzione si ottiene scambiando i ruoli di phi e phi*. Vale anche l\'implicazione opposta: se a = a*, allora a è un intero mod.p.
<BR>
<BR>------
<BR>Digressione:
<BR>Il primo fatto è il Teorema di Nonmiricordopiuchì, applicato al gruppo moltiplicativo di esso campo.
<BR>
<BR>Il secondo fatto non è troppo complicato da dimostrare. Basta sapere che anche in questi strani campi vale la Regola del Resto: un polinomio è divisibile per (x-a) sse a è radice. La uso su x^p-x.
<BR>
<BR>Il terzo fatto si prova scrivendo gli elementi del campo come a + b phi, con a e b interi mod p. (a+b phi)* = a + b phi* = a + b - b phi. E quest\'ultima rimane a + b phi sse b = 0.
<BR>[pensatela un po\' come la \"parte reale\" e la \"parte immaginaria\"...]
<BR>------
<BR>
<BR>Torniamo a noi e alla formula di Binet. Abbiamo che F<sub>p+1</sub> = 0 sse phi<sup>p+1</sup> = phi*<sup>p+1</sup>.
<BR>
<BR>Se elevo phi<sup>p+1</sup> alla potenza p-1, ottengo phi<sup>p^2-1</sup> = 1, per il primo fatto. Per il secondo fatto, phi<sup>p+1</sup> è in realtà un intero mod.p. Per il terzo fatto, phi<sup>p+1</sup> = (phi<sup>p+1</sup>)* = phi*<sup>p+1</sup>. Quindi vale il caso (iii).
<BR>
<BR>Conclusione:
<BR>
<BR>caso (i) sse 5 è r.q. mod.p
<BR>caso (ii) solo per p=5
<BR>caso (iii) sse 5 non è r.q. mod.p []
<BR>
<BR>Domani, se ho tempo, l\'altra con l\'algebra lineare...
<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."

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

Frattanto che risolvo il problema di Hit. vi propongo un altro problema molto simile...
<BR>
<BR>Dimostrare che p|F<sub>p-1</sub>+F<sub>p+1</sub>-1
<BR>
<BR>EDIT: scusatemi, mi sono sbagliato, ma non è necessario darmi subito addosso... <IMG SRC="images/forum/icons/icon_biggrin.gif"> P.S.: Hit, l\'ho risolto il tuo prob, adesso tu risolvi il mio <IMG SRC="images/forum/icons/icon_wink.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 30-11-2004 22:08 ]

Avatar utente
thematrix
Messaggi: 465
Iscritto il: 01 gen 1970, 01:00
Località: Quartu S.E. (CA)

Messaggio da thematrix » 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>Frattanto che risolvo il problema di Hit. vi propongo un altro problema molto simile...
<BR>
<BR>Dimostrare che p|F<sub>p-1</sub>+F<sub>p+1</sub>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>sarà per l\'ora(tarda),ma qualcosa non mi convince:
<BR>se F<sub>4</sub> = 3 e F<sub>6</sub> = 8,F<sub>4</sub>+F<sub>6</sub> = 11,ma 5 non divide 11.
<BR>
<BR>(ho il dubbio di essermi perso qualcosa,o di fare un errore cretino...) <IMG SRC="images/forum/icons/icon_cool.gif"> [addsig]
Sunshine or rain, it's all the same, life isn't gray
oh Mary-Lou.

(Mary-Lou --- Sonata Arctica)

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

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

No, matrix, non ti sei perso nulla! La condizione di divisibilità suggerita da Simo nella traccia del suo problema è incontestabilmente falsa!!! E ciò discende in modo diretto dalla soluzione al problema posto in origine dal buon marco.
<BR>
<BR>Infatti, per ogni primo naturale p =\\= 5: p | F<sub>p-1</sub> <!-- BBCode Start --><I>vel</I><!-- BBCode End --> p | F<sub>p+1</sub>. Dunque, se fosse: F<sub>p-1</sub> + F<sub>p+1</sub> = 0 mod p, ne dovrebbe discendere che, per ogni primo p € N\\{5}: gcd(F<sub>p-1</sub>, F<sub>p+1</sub>) >= p, il che è falso, dacché notoriamente, comunque scelti
<BR>m, n € N: gcd(F<sub>m</sub>, F<sub>n</sub>) = F<sub>gcd(m,n)</sub>. Il caso p = 5 è stato già trattato da matrix.
<BR>
<BR>DUBBIO: simo, non è che forse intendessi chiedere di dimostrare che p <!-- BBCode Start --><B>non</B><!-- BBCode End --> divide in alcun caso F<sub>p-1</sub> + F<sub>p+1</sub>, quando p è un primo intero > 2, uuuh?
<BR>
<BR>P.S.: anziché \"cazzeggiare\", dedicatevi adesso al mio bel <!-- BBCode Start --><I>problemino</I><!-- BBCode End -->, su... <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"«Non c\'è animale più stupido della marmotta - disse l\'etologo - sta ferma ore ed ore a contemplare il sole»\". \"«Non c\'è animale più stupido dell\'etologo - disse la marmotta - sta fermo ore ed ore a contemplare me»\". - Enzo Costa<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-11-2004 14:03 ]

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. Ecco la dimostrazione \"elementare\" che caratterizza i casi (i)-(iii).
<BR>
<BR>Tanto per fissare le idee, faccio due ragionamenti di esempio con il caso p = 13.
<BR>
<BR>La successione di Fibonacci modulo 13 è (0, 1, 1, 2, 3, 5, -5, 0, -5, -5, 3, -2, 1, -1, 0, ...). Da questo ricaviamo un po\' di idee: gli zeri hanno periodo T=7. Dopodiché la sequenza si ripete moltiplicata per la costante k=-5. Si vede che per cercare i periodi, non basta considerare gli elementi singolarmente, ma a coppie. E 7 non è il periodo vero di tutta la sequenza, ma lo è solo \"a meno di una costante\". Mmmmmh... viene in mente la retta proiettiva... lavoriamo un po\' su queste idee...
<BR>
<BR>----------------
<BR>
<BR>Dimostrazione geometrica:
<BR>
<BR>Una \"s.F.\" (sequenza di Fibonacci) è una successione in cui ogni termine, a partire dal terzo, è la somma dei due precedenti. I primi due termini della s.F. sono il \"seme\".
<BR>
<BR>Sono fatti ovvi: una s.F. è completamente determinata dal suo seme. Sommando termine a termine due s.F., ottengo un\'altra s.F., il cui seme è la somma dei semi delle due s.F. di partenza. Moltiplicando tutti i termini di una s.F: per una costante, ottengo una s.F. il cui seme è il seme iniziale, moltiplicato per la stessa c.te. Cancellando un certo numero di termini iniziali da una s.F., ottengo ancora una s.F.
<BR>
<BR>Se definisco come S<sub>0</sub> come la s.F. di seme (1,0), e come S<sub>1</sub> la s.F. di seme (0,1), la s.F. di seme (a,b) è ottenibile come a S<sub>0</sub> + b S<sub>1</sub>. Si noti che S<sub>1</sub> è la consueta successione di Fibonacci, e S<sub>0</sub> si ottiene da S<sub>1</sub> anteponendo un 1.
<BR>
<BR>Tali definizioni hanno perfettamente senso sia negli interi consueti, che modulo p. Fisso ora un numero primo p. Nei ragionamenti che seguono, le s.F. saranno sempre considerate mod.p.
<BR>
<BR>Le coppie di interi mod.p formano il \"piano (mod.p)\". Esso ha p<sup>2</sup> elementi e (0,0) è la sua origine. Dato un elemento diverso dall\'origine, chiamo l\'insieme dei suoi multipli la \"retta (mod.p)\" passante per esso. Ogni retta è formata dall\'origine e da altri p-1 elementi. In tutto esistono p+1 rette.
<BR>
<BR>Definisco la funzione F dal piano in sé così:
<BR>
<BR>F(x,y) := (y,x+y).
<BR>
<BR>Questa F permette di costruire le s.F., nel senso che, (x, y, z) sono tre termini consecutivi di una s.F. sse F(x,y) = (y,z). Per costruire la successione di Fibonacci S<sub>1</sub>, posso semplicemente partire dal suo seme (0,1) e applicare iterativamente la F.
<BR>
<BR>Sia r una retta. F è lineare e bigettiva, quindi le immagini di elementi di r formano una retta, quindi posso vedere F anche come funzione dall\'insieme delle rette in sé.
<BR>
<BR>Considero la successione delle rette che ottengo partendo dalla retta per (0,1) e applicando iterativamente la F. Essendo l\'insieme delle rette finito, prima o poi la successione si ripete e da lì in poi è ciclica. Dato però che la F è invertibile, la prima retta è anche la prima che si ripete. Ossia, la successione delle rette che contengono coppie successive della successione di Fibonacci, si ripete ciclicamente. Chiamo T il suo periodo.
<BR>
<BR>Per come ho definito le cose, si vedrà che T è anche il periodo con cui si presentano gli zeri in S<sub>1</sub>. Se dimostro che (i) p-1, oppure (ii) p, oppure (iii) p+1 è multiplo di T, allora ho provato la tesi. Dimostrerò che, detto R il numero delle soluzioni distinte negli interi mod.p del polinomio x<sup>2</sup> - x - 1, allora T | p+1-R. Dato che R può valere al massimo 2, questo concluderebbe la dimostrazione.
<BR>
<BR>Innanzi tutto osservo che F<sup>T</sup>(x,y) = (kx,ky) per un\'opportuna costante k non nulla (cioè è un\'omotetia mod.p). Inoltre risulta essere k = F<sub>T+1</sub>.
<BR>
<BR>Questo perché, per come ho scelto T, (F<sub>T</sub>, F<sub>T+1</sub>) appartiene alla retta di (0,1) (anzi, è la prima volta che ritorno su tale retta). Quindi (F<sub>T</sub>, F<sub>T+1</sub>) = (0, k). Da questo segue che gli zeri hanno periodo T.
<BR>
<BR>Inoltre, ripetendo il ragionamento con S<sub>0</sub>, che si ottiene anteponendo un 1, si ricava che F<sup>T</sup>(1,0) = (k,0). Per linearità, si ha che, per ogni punto (x,y) del piano, F<sup>T</sup>(x,y) = x F<sup>T</sup>(1,0) + y F<sup>T</sup>(0,1) = x (k,0) + y (0,k) = (kx,ky). Questo dimostra che F<sup>T</sup> è un\'omotetia di fattore k.
<BR>
<BR>In sostanza, partendo dalla retta di (0,1), applicando ripetutamente la F, ho trovato un ciclo di lunghezza T, che chiamerò la traiettoria di (0,1) nello spazio delle rette. Lo stesso discorso può essere fatto partendo da qualunque altro punto del piano (diverso dall\'origine) e individuare la sua traiettoria (che potrà essere o meno la stessa di (0,1)).
<BR>
<BR>Naturalmente non è detto che la traiettoria della retta di (0,1) copra tutte le rette. Tuttavia, ogni traiettoria deve essere di lunghezza sottomultipla di T. Questo perché F<sup>T</sup> è un\'omotetia, e quindi dopo T passi, si torna sempre sulla retta di partenza.
<BR>
<BR>Ora cerco quali sono le rette la cui traiettoria ha un solo elemento (ossia, che applicando F ai punti della retta si rimane sulla retta stessa; in altri termini, cerco gli autovettori di F).
<BR>
<BR>F(0,1) = (1,1), che stanno su rette diverse.
<BR>F(1,x) = (x,1+x). Stanno sulla stessa retta sse 1 + x = x<sup>2</sup> (e questo fatidico polinomio, presto o tardi, doveva saltare fuori!).
<BR>
<BR>Cioè le traiettorie lunghe 1 sono esattamente R. Le altre rette sono in tutto p + 1 - R, e vogliamo provare che T divide quest\'ultimo numero. Sia (x,y) un punto diverso da zero, la cui retta abbia traiettoria più lunga di 1. Diciamo che tale traiettoria sia lunga T\'. Ho già detto che T\' | T.
<BR>
<BR>Dico anche che T | T\'. Infatti, per ipotesi (x,y) e F(x,y) sono lin.indipendenti (*) (appartengono a rette diverse). Applicando F<sup>T\'</sup>, con un ragionamento analogo a quanto fatto per (0,1), troviamo che F<sup>T\'</sup> è un\'omotetia, e quindi tutte le traiettorie hanno lunghezza sottomultipla di T\'. Quindi T | T\'.
<BR>
<BR>(*) Questo è l\'unico fatto non elementare dell\'Algebra Lineare che ho usato. Una prova elementare può essere scritta osservando che, ponendo D = x<sup>2</sup> + xy - y<sup>2</sup>, sia ha che D =/= 0 (altrimenti sarei in una retta con traiettoria lunga 1). Allora posso risolvere i sistemi a.(x,y) + b.F(x,y) = (0,1) e c.(x,y) + d.F(x,y) = (1,0). Allora S<sub>0</sub> e S<sub>1</sub> possono essere ottenute come combinazione lineare delle s.F. con semi (x,y) e F(x,y). Allora, applicando F<sup>T\'</sup> a queste combinazioni, trovo l\'omotetia voluta. (/*)
<BR>
<BR>In definitiva, ci sono solo due tipi di traiettorie possibili: quelle lunghe 1 e quelle lunghe T. Le prime sono R. Tutte le altre hanno p + 1 - R elementi e sono disgiunte. Da questo segue che T | p + 1 - R. []
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>\"My soul is painted like the wings of butterflies
<BR>
<BR>Fairy tales of yesterday will grow but never die\"<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 30-11-2004 15:08 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

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

<!-- 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-27 10:32, HiTLeuLeR wrote:
<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, F<sub>p<sub>n</sub></sub> non sia divisibile per p<sub>k</sub>. <IMG SRC="images/forum/icons/icon24.gif">
<BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 27-11-2004 10:40 ]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR><!-- BBCode Start --><B>Lemma 1.</B><!-- BBCode End --> Se p|n e p==3 (mod 4) allora non possono esistere due interi tali che n=a²+b² e (a,b)=1.
<BR>Infatti se fosse così avremmo che p non divide nè a nè b e quindi avremmo che b ha un inverso che chiamiamo c (b*c==1 (mod p)). Quindi sarà a²==-b² (mod p) e quindi (ac)²==-1 (mod p). Ma per il piccolo th. di Fermat abbiamo che (ac)<sup>p-1</sup>==1 (mod p). Ma p-1==2 (mod 4) e quindi p-1=4k+2 per qualche k. Avremmo quindi che
<BR>1==((ac)²)<sup>2k+1</sup>==(-1)<sup>2k+1</sup>==-1 (mod p) cioè p=2. Assurdo.
<BR>
<BR><!-- BBCode Start --><B>Lemma 2.</B><!-- BBCode End --> F<sub>n+k</sub>=F<sub>n-1</sub>F<sub>k</sub>+F<sub>n</sub>F<sub>k+1</sub>
<BR>Abbiamo per induzione:
<BR>F<sub>n+0</sub>=F<sub>n-1</sub>F<sub>0</sub>+F<sub>n</sub>F<sub>1</sub>
<BR>F<sub>n+1</sub>=F<sub>n-1</sub>F<sub>1</sub>+F<sub>n</sub>F<sub>2</sub>
<BR>
<BR>Supponendolo vero per k e k+1 sommando le due uguaglianze si ottiene quella per k+2 (vi risparmio i conti)
<BR>
<BR>Ponendo k=n-1 abbiamo che F<sub>2n-1</sub>=F<sub>n-1</sub>²+F<sub>n</sub>² cioè che F<sub>2n-1</sub> è scomponibile nella somma di due quadrati primi tra loro. Quindi se p==3 (mod 4) p non può dividere, per il lemma 1, nessun numero di Fibonacci ad indice dispari. In particolare non divide nessun numero di Fibonacci avente come indice un numero primo (ricordiamo che F<sub>2</sub>=1 e quindi vale anche se il primo è 2) cioè la tesi.
<BR>
<BR>Ci basta ora dimostrare che i numeri primi congrui a 3 mod 4 sono infiniti. Per questo scomodiamo il carissimo Dirichlet il quale afferma che in una prograssione aritmetica a+kb dove a e b sono primi tra loro esistono infiniti primi. Noi prendiamo naturalmente a=3 e b=4.
<BR>
<BR>c.v.d.
<BR>

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

<!-- 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

Bloccato