eserciziaccio

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
edony
Messaggi: 204
Iscritto il: 01 gen 1970, 01:00
Località: Salerno

Messaggio da edony » 01 gen 1970, 01:33

determinare le ultime 5 cifre di 5^(5^5)...
<BR>Io con un procedimento veramente brutto mi trovo 03125 ma non ne sono affatto sicuro...spero che mi illuminiate con un procedimento brillante(se c\'è..)

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

Messaggio da fph » 01 gen 1970, 01:33

Suggerimento: congruenze + teorema cinese del resto
<BR>
<BR>...dovrebbe funzionare, non ho provato a rifarlo ma cose di questo tipo ne ho gia\' viste in passato (specialmente potenze di 5, vengono particolarmente bene)
<BR>--f
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Sono poco più che un novellino della teoria dei numeri, ma questo metodo funziona e non è troppo contoso (non so se sia la stessa cosa che voleva dire fph, o se la sua idea sia più raffinata...):
<BR>
<BR>- Vogliamo trovare le ultime 5 cifre dei numeri della successione a<sub>0</sub>=5, a<sub>n+1</sub>=5<sup>a<sub>n</sub></sup>.
<BR>
<BR>- a<sub>1</sub>=5<sup>5</sup>=3125.
<BR>
<BR>- Ipotizziamo che per i>0, tutti gli a<sub>i</sub> terminino per 03125, ovvero a<sub>i</sub>=10<sup>5</sup>k+3125, per qualche intero k.
<BR>
<BR>- Per dimostrarlo per induzione, è sufficiente far vedere che
<BR>5<sup>10<sup>5</sup>k+3125</sup>=5<sup>5</sup> (mod 10<sup>5</sup>).
<BR>
<BR>- Dividiamo tutto per 5<sup>5</sup>, ottenendo la relazione equivalente
<BR>5<sup>10<sup>5</sup>k+3120</sup>=1 (mod 2<sup>5</sup>).
<BR>
<BR>- Siccome phi(32)=16 e 5 e 32 sono coprimi, allora per il teorema di Fermat
<BR>5<sup>16k</sup>=1 (mod 32), per ogni k intero (o più elementarmente, facendo due conti, si trova che il periodo è addirittura 8).
<BR>
<BR>- Ma 10<sup>5</sup>k+3120 è multiplo di 16, quindi la relazione è verificata e l\'ipotesi fatta all\'inizio è dimostrata per induzione.[addsig]

fph
Site Admin
Messaggi: 3813
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-03-24 01:04, Antimateria wrote:
<BR>Sono poco più che un novellino della teoria dei numeri, ma
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Si\', certo, in aritmetica non-standard forse <IMG SRC="images/forum/icons/icon_smile.gif">
<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>- a<sub>1</sub>=5<sup>5</sup>=3125.
<BR>
<BR>- Ipotizziamo che per i>0, tutti gli a<sub>i</sub> terminino per 03125, ovvero a<sub>i</sub>=10<sup>5</sup>k+3125, per qualche intero k.
<BR>
<BR>- Per dimostrarlo per induzione, è sufficiente far vedere che
<BR>5<sup>10<sup>5</sup>k+3125</sup>=5<sup>5</sup> (mod 10<sup>5</sup>).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>C\'e\' qualcosa che non mi quadra... forse c\'e\' stata un po\' di confusione con gli indici, ma cosi\' mi viene che a_1=125 =/= 3125 mod 10000...
<BR>
<BR>In generale, cmq, il metodo e\':
<BR>1) con il TCR spezzare la congruenza in due congruenze gemelle:
<BR>x==3125 (mod 2^5)
<BR>x==3125 (mod 5^5)
<BR>
<BR>2) risolvere separatamente: la seconda congruenza e\' verificata automaticamente a causa dello sfracello di fattori 5 presenti nel numero x;
<BR>la prima si fa a mano calcolandosi il periodo di 5 mod 32.
<BR>Poi in realta\', volendo ridurre il lavoro manuale al minimo, c\'e\' un risultatillo di algebra che dice che il periodo di 5 mod 2^n (per n>=3) e\' sempre 2^(n-2), ed e\' il piu\' alto periodo possibile mod 2^n.
<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
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 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-03-24 17:00, fph wrote:
<BR>C\'e\' qualcosa che non mi quadra... forse c\'e\' stata un po\' di confusione con gli indici, ma cosi\' mi viene che a_1=125 =/= 3125 mod 10000...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Non capisco cosa intendi, a me quadra tutto.

edony
Messaggi: 204
Iscritto il: 01 gen 1970, 01:00
Località: Salerno

Messaggio da edony » 01 gen 1970, 01:33

Dunque vediamo se ho capito bene...il TCR ci assicura che se x=a modMN allora x=a modM e x=a modN,senza dare per scontato che sia 3125 il risultato imposto il sistema
<BR>x=5^(5^5) mod2^5
<BR>x=5^(5^5) mod 5^5
<BR>la seconda ha soluzioni x=3125k
<BR>la prima x=3125 + h2^5, quindi l\'unica soluzione è 3125(k=1,h=0)
<BR>Se nn ho capito qualcosa ditemelo,se non ho capito niente sparatemi..(BANG!)

fph
Site Admin
Messaggi: 3813
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-03-24 19:14, Antimateria wrote:
<BR>Non capisco cosa intendi, a me quadra tutto.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Dubbio risolto, ero io che davo i numeri <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>Edony:
<BR>la seconda ha soluzioni x=3125k
<BR>la prima x=3125 + h2^5, quindi l\'unica soluzione è 3125(k=1,h=0)
<BR>
<BR>Giusto, anche se forse senza sapere a priori il risultato e\' piu\' difficile risolvere le congruenze.
<BR>Forse ti eri semplicemente dimenticato di scriverlo, cmq preciso: la soluzione e\' unica mod 10000 (3125*32), e le sol sono k=1-32n, h=3125n (con n intero anche negativo). Il TCR infatti fornisce soluzioni mod MN.
<BR>
<BR>ciao!
<BR>--f
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: fph il 25-03-2004 01:00 ]
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 01 gen 1970, 01:33

5<sup>(5<sup>5</sup>)</sup> = 191101259794547752035640455970396459919808104899009433713951278924652053024261\\
<BR>580301205938651973985026558644015579446223535921278867380697228841014691598660\\
<BR>208796189675719570183928166033804761122597553362610100148265112341314776825241\\
<BR>149309444717696528275628519673751439535754247909321920664188301178716912255242\\
<BR>107005070906467438287085144995025658619446154318351137984913369177992812743384\\
<BR>043154923685552678359637410210533154603135372532574863690915977869032826645918\\
<BR>298381523028693657287369142264813129174376213632573032164528297948686257624536\\
<BR>221801767322494056764281936007872071383707235530544635615394640118534849379271\\
<BR>951459450550823274922160584891291094518995994868619954314766693801303717616359\\
<BR>259447974616422005088507946980448713320513316073913423054019887257003832980124\\
<BR>605019701346739717590902738949392381731578699684589979478106804282243609378394\\
<BR>633526542281570430283244238551508231649096728571217170812323279048181726832751\\
<BR>011274678231741098588868370852200071173349225391332230075614718042900752767779\\
<BR>335230620061828601245525424306100689480544658470482065098266431936096038873625\\
<BR>851074707434063628697657670269925864995355797631817390255089133122329474393034\\
<BR>395616132833407283166349825814522686200430779908468810380418736832480090387359\\
<BR>621291963360258312078167367374253332287929690720549059562140688882599124458184\\
<BR>237959786347648431567376092362509037151179894142426227022006628648686786871018\\
<BR>298087280256069310194928083082504419842479679205890881711232719230145558291674\\
<BR>679519743054802640464685400273399386079859446596150175258696581144756851004156\\
<BR>868773090371248253534383928539759874945849705003822501248928400182659005625128\\
<BR>618762993804440734014234706205578530532503491818958970719930566218851296318750\\
<BR>174353596028220103821161604854512103931331225633226076643623668829685020883949\\
<BR>614283048473911399166962264994856368523471287329479668088450940589395110465094\\
<BR>413790950227654565313301867063352132302846051943438139981056140065259530073179\\
<BR>077271106578349417464268472095613464732774858423827489966875505250439421823219\\
<BR>135722305406671537337424854364566378204570165459321815405354839361425066449858\\
<BR>540330746646854189014813434771465031503795417577862281177658587694168090820312\\
<BR>5
In the break of new dawn
My hope is forlorn
Shadows they will fade
But I'm always in the shade
Without you...

My Selene - Sonata Arctica

Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da bh3u4m » 01 gen 1970, 01:33

Le ultime cifre sono appunto 03125. Il problema è risolto.
In the break of new dawn
My hope is forlorn
Shadows they will fade
But I'm always in the shade
Without you...

My Selene - Sonata Arctica

edony
Messaggi: 204
Iscritto il: 01 gen 1970, 01:00
Località: Salerno

Messaggio da edony » 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-03-25 01:00, fph wrote:
<BR>
<BR>Giusto, anche se forse senza sapere a priori il risultato e\' piu\' difficile risolvere le congruenze.
<BR>Forse ti eri semplicemente dimenticato di scriverlo
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ti assicuro che il rislutato nn c\'era bisognava trovarlo non darne una dimostrazione, ma d\'altra parte era un esercizio di selezione per il s.anna non ci si poteva aspettare che fosse totalmente olimpico

Bloccato