OliForum Matematico

determinare le ultime 5 cifre di 5^(5^5)...
 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\'è..)

Suggerimento: congruenze + teorema cinese del resto
 
 ...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)
 --f

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...):
 
 - Vogliamo trovare le ultime 5 cifre dei numeri della successione a0=5, an+1=5an.
 
 - a1=55=3125.
 
 - Ipotizziamo che per i>0, tutti gli ai terminino per 03125, ovvero ai=105k+3125, per qualche intero k.
 
 - Per dimostrarlo per induzione, è sufficiente far vedere che
 5105k+3125=55 (mod 105).
 
 - Dividiamo tutto per 55, ottenendo la relazione equivalente
 5105k+3120=1 (mod 25).
 
 - Siccome phi(32)=16 e 5 e 32 sono coprimi, allora per il teorema di Fermat
 516k=1 (mod 32), per ogni k intero (o più elementarmente, facendo due conti, si trova che il periodo è addirittura

.
 
 - Ma 105k+3120 è multiplo di 16, quindi la relazione è verificata e l\'ipotesi fatta all\'inizio è dimostrata per induzione.[addsig]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-03-24 01:04, Antimateria wrote:
 Sono poco più che un novellino della teoria dei numeri, ma
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Si\', certo, in aritmetica non-standard forse <IMG SRC="images/forum/icons/icon_smile.gif">
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 - a1=55=3125.
 
 - Ipotizziamo che per i>0, tutti gli ai terminino per 03125, ovvero ai=105k+3125, per qualche intero k.
 
 - Per dimostrarlo per induzione, è sufficiente far vedere che
 5105k+3125=55 (mod 105).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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...
 
 In generale, cmq, il metodo e\':
 1) con il TCR spezzare la congruenza in due congruenze gemelle:
 x==3125 (mod 2^5)
 x==3125 (mod 5^5)
 
 2) risolvere separatamente: la seconda congruenza e\' verificata automaticamente a causa dello sfracello di fattori 5 presenti nel numero x;
 la prima si fa a mano calcolandosi il periodo di 5 mod 32.
 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.
 
 ciao!
 --f

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-03-24 17:00, fph wrote:
 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...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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
 x=5^(5^5) mod2^5
 x=5^(5^5) mod 5^5
 la seconda ha soluzioni x=3125k
 la prima x=3125 + h2^5, quindi l\'unica soluzione è 3125(k=1,h=0)
 Se nn ho capito qualcosa ditemelo,se non ho capito niente sparatemi..(BANG!)

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-03-24 19:14, Antimateria wrote:
 Non capisco cosa intendi, a me quadra tutto.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Dubbio risolto, ero io che davo i numeri <IMG SRC="images/forum/icons/icon_smile.gif">
 
 Edony:
 la seconda ha soluzioni x=3125k
 la prima x=3125 + h2^5, quindi l\'unica soluzione è 3125(k=1,h=0)
 
 Giusto, anche se forse senza sapere a priori il risultato e\' piu\' difficile risolvere le congruenze.
 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.
 
 ciao!
 --f
 [ Questo Messaggio è stato Modificato da: fph il 25-03-2004 01:00 ]

5(55) = 191101259794547752035640455970396459919808104899009433713951278924652053024261\\
 580301205938651973985026558644015579446223535921278867380697228841014691598660\\
 208796189675719570183928166033804761122597553362610100148265112341314776825241\\
 149309444717696528275628519673751439535754247909321920664188301178716912255242\\
 107005070906467438287085144995025658619446154318351137984913369177992812743384\\
 043154923685552678359637410210533154603135372532574863690915977869032826645918\\
 298381523028693657287369142264813129174376213632573032164528297948686257624536\\
 221801767322494056764281936007872071383707235530544635615394640118534849379271\\
 951459450550823274922160584891291094518995994868619954314766693801303717616359\\
 259447974616422005088507946980448713320513316073913423054019887257003832980124\\
 605019701346739717590902738949392381731578699684589979478106804282243609378394\\
 633526542281570430283244238551508231649096728571217170812323279048181726832751\\
 011274678231741098588868370852200071173349225391332230075614718042900752767779\\
 335230620061828601245525424306100689480544658470482065098266431936096038873625\\
 851074707434063628697657670269925864995355797631817390255089133122329474393034\\
 395616132833407283166349825814522686200430779908468810380418736832480090387359\\
 621291963360258312078167367374253332287929690720549059562140688882599124458184\\
 237959786347648431567376092362509037151179894142426227022006628648686786871018\\
 298087280256069310194928083082504419842479679205890881711232719230145558291674\\
 679519743054802640464685400273399386079859446596150175258696581144756851004156\\
 868773090371248253534383928539759874945849705003822501248928400182659005625128\\
 618762993804440734014234706205578530532503491818958970719930566218851296318750\\
 174353596028220103821161604854512103931331225633226076643623668829685020883949\\
 614283048473911399166962264994856368523471287329479668088450940589395110465094\\
 413790950227654565313301867063352132302846051943438139981056140065259530073179\\
 077271106578349417464268472095613464732774858423827489966875505250439421823219\\
 135722305406671537337424854364566378204570165459321815405354839361425066449858\\
 540330746646854189014813434771465031503795417577862281177658587694168090820312\\
 5

Le ultime cifre sono appunto 03125. Il problema è risolto.

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-03-25 01:00, fph wrote:
 
 Giusto, anche se forse senza sapere a priori il risultato e\' piu\' difficile risolvere le congruenze.
 Forse ti eri semplicemente dimenticato di scriverlo
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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

OliForum Matematico

eserciziaccio