Puzzle time - number theory
-
It's still 41. Just do it in 2 stages.
23^9 yields 63. Euler's theorem tells us period 20 again.
so 63^9
last 2 digits are 41.
Is it a coincidence that it came out to 41 still? Or does that have to do with some congruence property of modular arithmetic?
"You never know what worse luck your bad luck has saved you from."
-Cormac McCarthy -
-
I have a great solution, let’s put the words ‘puzzle time’ in the title from now on so the 4-5 people who show interest can open the thread and others will know not to.
-
It's still 41. Just do it in 2 stages.
23^9 yields 63. Euler's theorem tells us period 20 again.
so 63^9
last 2 digits are 41.
Is it a coincidence that it came out to 41 still? Or does that have to do with some congruence property of modular arithmetic?
@jon-nyc said in Puzzle time - number theory:
It's still 41. Just do it in 2 stages.
23^9 yields 63. Euler's theorem tells us period 20 again.
so 63^9
last 2 digits are 41.
Is it a coincidence that it came out to 41 still? Or does that have to do with some congruence property of modular arithmetic?
No, that's not correct. You have to "nest" two applications of Euler's theorem to account for the nested exponentials.
-
The answer is 23.
You want "mod 100" for the result.
Phi(100) is 40.
Phi(40) is 16.
Now:
456 = 28 * 16+8, so 456 = 8 (mod 16)
789 = 19 * 40+29, so 789 = 29 (mod 40)
123 = 100 * 1 + 23, so 123 = 23 (mod 100)Hence, according to Euler:
123^789^456 mod 100 = 23^29^8 mod 100.Now, since 29 = -11 (mod 40): (with all = mod 100):
23^29^8 = 23^(-11)^8 = 23^(-11^2)^4 = 23^121^4
and, since 121 = 1 (mod 40),
23^121^4 = 23^1^4 = 23. -
Oh well.
I thought about attacking this with a binomial expansion, treating this like (a+b)^n with a=100 and b=23.
Doing the expansion even with a very high n wouldn’t be a big deal, since all the terms with an a in them could be ignored.
But still that left me with 23^789 which still required Euler to address.
