Puzzle time - number theory

[Klaus]

What are the last two digits of 123^789^456 ?

(^ is exponentiation).

[jon-nyc]

Euler’s theorem tells me that powers of 23 mod 100 cycle with period 20.

So 123^(789 * 456) = 23 ^ (9*16) = 23^144 = 23^4.

So 41

Interpret those equal signs as congruence signs.

[Klaus]

You are on the right track with Euler's theorem, but exponentiation is in mathematical convention a right associative operation, so it's 123^789^456 = 123^(789^456).

[jon-nyc]

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?

[George K]

You guys need to set up a subforum where you can circle-jerk discuss these things, LOL.

[Horace]

The puzzles are a bit much. jon loves them, I accept that, but I'm not sure they need to be shared everywhere. And I'm definitely not sure of the motivation. These are IQ tests, just by the bye.

[jon-nyc]

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.

[George K]

@jon-nyc said in Puzzle time - number theory:

I have a great solution, let’s put the words ‘puzzle time’ in the title

(I got the sarcasm...)

[Klaus]

@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.

[jon-nyc]

But the answer is right.

It’s just a coincidence that I got 41 both times, right?

[Klaus]

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.

[jon-nyc]

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.

[jon-nyc]

But it does offer a nice proof that the last two digits of a number are sufficient to determine the last two numbers of a power of that number.