PR 4 # 32

[alpertron]

Originally Posted by R.D. Silverman

While you got the right answer, you ignored the hint. There is a
MUCH easier way to do this.

Well, the derivation above was easy.

It is more interesting to find the last 7 digits of 7^(7^(7^(7^(7^(7^7))))) which is not too difficult.

[alpertron]

Originally Posted by alpertron

It is more interesting to find the last 7 digits of 7^(7^(7^(7^(7^(7^7))))) which is not too difficult.

Let x = 7^(7^(7^(7^(7^(7^7)))))
Let a = 7^(7^(7^(7^(7^7))))
Let b = 7^(7^(7^(7^7)))
Let c = 7^(7^(7^7))
Let d = 7^(7^7)
Let e = 7^7

x = 7^a = 7^(a mod phi(10000000)) (mod 10000000)
x = 7^a = 7^(a mod 4000000) (mod 10000000)

a = 7^b = 7^(b mod phi(4000000)) (mod 4000000)
a = 7^b = 7^(b mod 1600000) (mod 4000000)

b = 7^c = 7^(c mod phi(1600000)) (mod 1600000)
b = 7^c = 7^(c mod 640000) (mod 1600000)

c = 7^d = 7^(d mod phi(640000)) (mod 640000)
c = 7^d = 7^(d mod 256000) (mod 640000)

d = 7^e = 7^(e mod phi(256000)) (mod 256000)
d = 7^e = 7^(e mod 102400) (mod 256000)

Working backwards:

e = 7^7 = 4343 (mod 102400)
d = 7^4343 = 244343 (mod 256000)
c = 7^244343 = 372343 (mod 640000)
b = 7^372343 = 372343 (mod 1600000)
a = 7^372343 = 1172343 (mod 4000000)
x = 7^1172343 = 5172343 (mod 10000000)

So the last 7 digits of the power is 5172343.