Newsgroup: it.hobby.enigmi
Titolo: torre di potenze

Ho trovato, in una raccolta di enigmi di rec.puzzles, il seguente quesito:
==> arithmetic/digits/least.significant/tower.of.power.p <==
What are the least significant digits of 9^(8^(7^(6^(5^(4^(3^(2^1))))))) ?
Lascio un po' di spazio per chi non vuole sapere la soluzione...
Questa e' la soluzione allegata alla domanda:
==> arithmetic/digits/least.significant/tower.of.power.s <==
9^11 = 9 (mod 100), so we need to find 8^...^1 (mod 10).
8^5 = 8 (mod 10), so we need to find 7^...^1 (mod 4).
7^3 = 7 (mod 4), so we need to find 6^...^1 (mod 2), but
this is clearly 0, so 7^...^1 = 1 (mod 4) ==>
8^...^1 = 8 (mod 10) ==> 9^...^1 = 9^8 (mod 100) = 21 (mod 100)
Ma io non capisco una cosa: dice che 9^11 = 9 (mod 100), e quindi e' 
sufficiente trovare l'esponente di 9, cioe' 8^...^1 (mod 10). Ma perche' 
(mod 10) e non (mod 11), visto che le ultime due cifre delle potenze di 9 
si ripetono ogni 11 esponenti, e non ogni 10?
Stessa cosa per le altre considerazioni che vengono fatte: 8^5=8 mod 10, 
quindi e' sufficiente trovare l'esponente di 8 modulo 4. Perche' 4 e non 5? 
Mi sembra che cosi' venga lasciato indietro sempre un possibile valore.

 si ripetono ogni 11 esponenti, e non ogni 10?
Intanto c'è un errore: 9^40 = 1 (mod 100) per il teorema di Eulero, 
considerando che ci sono 40 numeri coprimi con 100 che sono < 100.
detto questo, supponi che l'esponente del 9 sia della forma 40m+n :
9^(40m+n) = (9^40)^m + 9^n = 1^m + 9^n = 9^n
quindi quello che conta è l'esponente modulo 40.
9^41 = 9 ---> 9^40 = 1, ecco perché scala di 1.

 Intanto c'è un errore: 9^40 = 1 (mod 100) per il teorema di Eulero,
Ma anche 9^11 = 9 mod 100 (basta provare). Secondo me la soluzione e' 
giusta, ma devo capire perche' scala di uno quell'esponente. Tu dici che 
gli basta sapere che 9^10=1 mod 100? 
Insomma, so che le ultime due cifre delle potenze di 9 si ripetono ogni 11 
esponenti. Quindi mi basterebbe conoscere l'esponente di nove modulo 11. 
Lui dice che gli basta conoscere quell'esponente modulo 10, perdendo quindi 
il valore 10. 
Boh.

 Boh.

calcolare quelle potenze?)
Non e' una questione di Euler totient function? phi(p)=p-1,
phi(p^n)=p^n-p^(n-1), phi moltiplicativa. Poi c'e' un teorema sul
valore di a^phi(qualcosa)=1 mod qualcosa.
La teoria dei numeri non e' assolutamente il mio forte.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
"You know, I've gone to a lot of psychics, and they've told me a lot of
different things, but not one of them has ever told me 'You are an
undercover policewoman here to arrest me.'"

 9^0=1...
Bene, pero' ci ho pensato ancora un po' e mi sono accorto che non e' un 
ragionamento corretto. Prendiamo per esempio le potenze di 8:
8^0=1
8^1=8
8^2=64
8^3=512
8^4=4096
8^5=32768
8^6=262144
8^7=2097152
8^8=16777216
...
E' vero che 8^5=8 mod 10, ma non e' vero che 8^4=1 mod 10. Dunque rimane il 
mio dubbio: la soluzione del giochino dice che siccome 8^5=8 mod 10 e' 
sufficiente trovare le potenze di 8 modulo 4. Ma se l'esponente di 8, cioe' 
7^6^5^4^3^2^1, fosse uguale a 4 (mod 5)? 
Continuo a non capire perche' diminuisce di uno il periodo... Forse usa la 
funzione modulo con valori non compresi tra 0 e n-1 ma tra 1 e n? In questo 
caso escluderebbe solo l'esponente 0 (senza modulo), e questo sarebbe 
accettabile.
Qualcuno ha voglia di provare a pensarci?

 Qualcuno ha voglia di provare a pensarci?
8 e 10 non sono primi tra loro, quindi non vale il tuo ragionamento.
pazqo

Continuo a non capire perche' diminuisce di uno il periodo... 
Cosa si intende con periodo? Bisogna fare attenzione che le potenze di
8 (mod 10) *non* costituiscono un gruppo. Comunque, in un gruppo, se
x^n=x, cio' significa che il periodo (definito come il minimo
esponente p, se esiste, tale che x^p = 1) di x e' n-1 e non n. Quindi
non si diminuisce niente di uno. Ciao 

 8 (mod 10) *non* costituiscono un gruppo. 
Mi riferisco alla soluzione proposta da quel testo che ho trovato, che 
riporto qua sotto:
==> arithmetic/digits/least.significant/tower.of.power.s <==
9^11 = 9 (mod 100), so we need to find 8^...^1 (mod 10).
8^5 = 8 (mod 10), so we need to find 7^...^1 (mod 4).
7^3 = 7 (mod 4), so we need to find 6^...^1 (mod 2), but
this is clearly 0, so 7^...^1 = 1 (mod 4) ==>
8^...^1 = 8 (mod 10) ==> 9^...^1 = 9^8 (mod 100) = 21 (mod 100)
Non capisco tutti quei passaggi "so we need to find...". Se noti, ogni 
volta scopre che un numero elevato a un certo esponente e' uguale a se 
stesso (dopo aver usato un opportuno modulo) e nel passaggio successivo 
quell'esponente viene calato di uno e usato come modulo.
Mi spiego meglio: dice che 9^11=9 mod 100 e quindi ci resta da trovare il 
valore dell'esponente di 9 modulo _10_. Perche' non modulo 11? E cosi' via 
negli altri passaggi. Alla fine dice 7^3=7 mod 4, quindi e' sufficiente 
trovare 6^5^4^3^2^1 modulo 2. A me sembra che escluda la possibilita' che 
6^5^4^3^2^1 sia uguale a 2 modulo 3.

6^5^4^3^2^1 sia uguale a 2 modulo 3.
Il modulo 3 non c'entra nulla. Ciao

 Ripeto: se x^p = x (mod n), p non e' il periodo di x, ma p-1.
Questo e' chiaro, ma non mi spiego questa situazione:
8^0=1 mod 10
8^1=8 mod 10
8^2=4 mod 10
8^3=2 mod 10
8^4=6 mod 10
8^5=8 mod 10
Quindi il periodo e' 4, le cifre che si ripetono sono 8, 4, 2, 6, ma 
quell'1 iniziale che non ri ripete piu'? Non lo considera solo perche' sa 
per certo che l'esponente di 8 non e' 0?

per certo che l'esponente di 8 non e' 0?
Perche' sa per certo che 8^0 non si ripete piu': fa parte dell'
"antiperiodo" mod 10. Ciao