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\'è..)
eserciziaccio
Moderatore: tutor
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
<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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
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
.
<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]
<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
.<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]
<!-- 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
<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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
<!-- 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.
<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.
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!)
<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!)
<!-- 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 ]
<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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
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
<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
My hope is forlorn
Shadows they will fade
But I'm always in the shade
Without you...
My Selene - Sonata Arctica
<!-- 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
<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