# Challenge 91: The Last Three Digits of a Phi-Exponent Tower

Share
Embed
• Published on May 2, 2019
• Congratulations to Juju Mas, Jonathan Liu, driudwaker, Emmett Nelson, Bigg Barbarian, Richard Chen, Mokou Fujiwara, and Serengeti Ghasa for successfully solving the last week's math challenge question! Juju Mas was the first person to solve the question.
Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
For more Weekly Math Challenges:

## Comments • 64

• LetsSolveMathProblems  4 months ago +7

Due to the freezing weather in Boston, where I spent the past weekend, I have still not quite recovered from cold, not to mention the end-of-the-school-year workload I have yet to conquer. I will strive to post the solution to the last week's challenge by this Saturday at the latest. I sincerely apologize for the delay. The solution to the last week's challenge was 3 crash tests.

• Patrick Salhany 4 months ago

@LetsSolveMathProblems how old are you ?

• Jonathan Liu 4 months ago +1

Get well soon!

• Mr L 4 months ago

@LetsSolveMathProblems yes, it's redundant!

• LetsSolveMathProblems  4 months ago +5

@Mr L By convention, a^b^c denotes a^(b^c). Note that it would not make much sense to use a^b^c to denote (a^b)^c because (a^b)^c = a^(b*c).

• Mr L 4 months ago +2

Is it a^(b^c) or (a^b)^c?

• Electro SchOOp 4 months ago +2

The answer is between 0 and 999

• Mokou Fujiwara 4 months ago

Good bye Heisei, and greetings Reiwa. First problem solved in Reiwa Era.
Φ(n) is Euler's Totient Functions, with useful properties:
a) Φ(a^b) = a^(b-1) Φ(a)
b) a^Φ(b)≡1 if a and b are coprime
c) Φ(p) = p-1 for all prime numbers p
Chinese Remainder Theorem is also a useful tool for this problem.
Let's write the power tower as T(3,2019). We want to find T(3,2019) mod 1000.
T(a,b) = [Φ(a^2)] ^ T(a+1,b) for all positive integers a,b, and a

• Rafael 4 months ago

i saw a triple integral some time ago and could never solve it even with computational methods, if someone wants to accept this challenge go ahead... "integral from 0 to a, integral from 0 to a, integral from 0 to a, of the function [1/((x^2+y^2+z^2)^(3/2)] dxdydz"

• Jaime Araujo 4 months ago +1

what happens if you try to do it like a polar coordinates but in trhee dimensions because it looks really similar to a gaussian integral

• Karthasis 4 months ago

• Midas Schonewille 4 months ago +2

I think it's 256

The only relevant values of ϕ(n) we need are:
ϕ(3^2) = 6

ϕ(4^2) = 8
ϕ(5^2) = 20
The equation can be written as 6^(8^(20^N)) where N is some big positive integer.
The last 2 digits of powers of 8 cycle with a period of 20, so the last 2 digits of 8^20 are equal to those of 8^40 and also to those of 8^(20^N). The last 2 digits of 8^20 are 76, so those are also the last 2 digits of 8^(20^N).
The last 3 digits of powers of 6 cycle with a period of 25. 8^(20^N) ends with 76, so it's one bigger than a multiple of 25. The last 3 digits of 6^26 are equal to those of 6^51 and also to those of 6^(8^(20^N)). The last 3 digits of 6^26 are 256, so those are also the last 3 digits of 6^(8^(20^N)).
So the answer is 256.

• Nicolas Nauli 4 months ago +1

The answer is 256.

Firstly, we find the value of the base, phi(9). The squared form actually helps us in finding the factors of the input that we should exclude as they are definitely not coprime with the input.

phi(9) = 6
From this being the base, we directly know that the last digit has to be 6. If we keep multiplying by 6 the last digit will always be 6.
*Last digit = 6*

The last digit always being the same no matter what actually helps us to find the second last digit!
when we keep multiplying by 6, the second last digits in order will be: 0, 3, 1, 9, 7, 5, 3....
As we can see, the pattern repeats every time we multiply 6 five times, or basically multiply by 6^5 (after 0 though).

Therefore we want to find which (mod 5) matches with the exponent of the first base. Therefore we must find the value of the second base.
phi(16) = 8 because any number below 16 must be odd to be relatively prime with 16.
So now we want to find the question mark: 8^phi(25)^phi(36).... = ? (mod 5)

The thing about (mod 5) is that we only need to look at the last digit to know which term the number is in the (mod 5) *world* (inspired by bprp).
8^phi(25)^phi(36).... could have any last digit, or can it? Well, since we are only looking at last digits, we just need to multiply 8 and find out that the pattern this time is: 8, 4, 2, 6, 8....

This time, we go to the (mod 4) world. Before we can proceed any further, we need to find the next base phi(25). We know we are after the multiples of 5. We exclude 5, 10, 15, 20 and of course 25 itself. Therefore the number of remaining coprime integers is 25 - 5 = 20. phi(25) = 20

This is great! Because we know that 20 is divisible by 4, therefore no matter what you raise 20 to the power of, you will get a multiple of 4. And so that means the last digit of 8^20^phi(36) should be the 4th digit in this previous sequence: 8, 4, 2, 6, 8. Which is 6. Knowing this tells us that 8^20^phi(36) = 1 (mod 5).

Yay! We can now get our 2nd last digit. Recall that the 2nd last digit's repeating sequence is 0, 3, 1, 9, 7, 5, 3....
But don't forget that the whole 8^20^phi(36).... is 1 (mod 5), including the 0 from the start of the sequence. Since it is the only one that doesn't repeat, we have to exclude it, to get the correct position of the 2nd last digit. So from the sequence 3, 1, 9, 7, 5, 3.... , we get 0 (mod 5) because we exclude the 0, and minus one. *This show that 2nd last digit is the 5th number from the sequence which happens to be 5.*

For the 3rd last digit, this digit depends on the 2nd and 1st digit. They both affect the 3rd last digit. And we happen to now know that the last two digits are 56. Therefore, we only need to choose powers of 6 with last 3 digits that have 56 being the last two digits.
We record them down, but we only to skip 6^5 every time since 56 repeats every 5 times.
The sequence for the 3rd last digits are: 6, 0, 4, 8, 2, 6....

Well, well, well, we seem to meet with the (mod 5) world again. But we cannot just directly find it in (mod 5), because it is only repeating every 5 times only if the last two digits are 56, or, when we multiply by 6^5, instead of 6 every time. Therefore we join both the 6^5 and the new (mod 5) which gives us the problem of finding (mod 25). We want to find 8^20^phi(36).... = ? (mod 25) now. It is (mod 25) because it is asking for which (mod 5) every time I multiply 6^5 and since we have the exponent already being every 5 from the 6^5, we mustn't forget to multiply by another 5. We know 8^20^phi(36).... is amongst 1, 6, 11, 16, 21 (mod 25) (because it has the 0 from last time and this is what I mean by already multiplying by 6^5).

Luckily, 25 is a factor of 100, which means we only need to find the last two digits of 8^20^phi(36).... to get it in the (mod 25) world. Previously, we found out that it's last digit only is 6.
Now record the 2nd last digits which have 6 being the last digit and also don't forget that the last digit repeats every 4 times (based on the previous (mod 4): 9, 1, 3, 5, 7, 9....

It's (mod 5) again! Just like the 6^5 and the (mod 5) joining into (mod 25), we also have 8^4 and the other new (mod 5) joining into (mod 20) and at this moment, I went WOW. The number is 6^8^*20*....
Now we totally know that the 2nd exponent has to be 0 (mod 20). This means that it is 0 (mod 5) for 9, 1, 3, 5, 7, 9... which is the 5th number: 7.
That means that the last two digits of 8^20.... is 76 which means that it is also 1 (mod 25).

And since we have still have been counting that extra 0 from just now, we deduct by 1, giving us 0 (mod 25) to pick from 6, 0, 4, 8, 2, 6....
*Finally, the 3rd last digit is the 5th digit of the sequence, which is 2.*

This gives our answer of 256.

• Nicolas Nauli 4 months ago

@Sam soum ah, thats because the last digit of 6^n is always 6, and think mod 10 as multiples of 10, because it is xd, 0 mod 10 would look like 10, 20, 30 and so on. 1 mod 10 would look like 11, 21, 31 and so on. Do you see a pattern? Yes, the neat thing about mod 10 is you only need to look at the last digit, because every time you finish a 'period' of 10, you jump to the next level, or basically you just increase the second last digit by one every time, since you add only by ten everytime

• Sam soum 4 months ago

@Nicolas Nauli why is 6^n congruent to 6 mod 10 ? im having a hard time

• Nicolas Nauli 4 months ago

@Mokou Fujiwara Nice, I literally like to do math challenges everyday as well, I dont bother with the ones i already can. And it doesnt have to challenges I find in the internet, it could be solving my own questions of why a formula is like this, or is it true that this pattern repeats, and just like to think about the philosophy of math. I also frequently do these at night, so unless I am satisfied with my answer I cant go to sleep xd.

• Mokou Fujiwara 4 months ago

I just learnt some on Google, some when I was in University (and do the revision for this problem). I do the challenges for fun and keep my brain healthy.

• Nicolas Nauli 4 months ago

@Mokou Fujiwara haha, thats because I dont have much knowledge about number theory except basic modular arithmetic, we're not really taught number theory much in high school in my country :)

• Arghyadeep Chatterjee 4 months ago +2

The answer is 256.
The problem is 6^8^20^12^......
When this is divided by 8 , the remainder is 0
We need to find the remainder when this is divided by 125.
We need to find what is 8^20^12 mod 100 .
this is 0 mod 4 and obviously 1 mod 25 (as phi(25) = 20 and gcd(8,25) = 1)
So the number is 76 mod 100
So we need to find 6^76 mod 125
Which after a little calculation gives 6 mod 125
So the number we want is 6 mod 125 and 0 mod 8. Use Chinese Remainder Theorem or Euclid's division algorithm or by direct observation that 256 satisfies both conditions. So answer is 256

• Serengeti Ghasa 4 months ago

The answer is 256
⍉(3²)=6
⍉(4²)=8
⍉(5²)=20
⍉(6²)=13
let a =20ˣ=0mod100
let b =8ᵃ=376mod1000 as 8¹⁰⁰=376mod1000 =76mod100
6ᵇ=(376× 176⁷×6⁶)mod1000
=256mod1000
as 6¹⁰⁰ˣ=376mod1000
6¹⁰=176mod1000
with love
Prabhat Kumar Sahu
Singhijuba

• Evyatar Baranga 4 months ago +1

The answer is 1
Phi is Euler's function, so it has the property a^phi(n) = 1 mod n.
We want to find the last three digits - the value mod 1000, so if we have phi(1000) anywhere in this power tower then everything would become 1(some junk to the power of phi(1000)->1, and 1 to the power of anything is still 1).
Another property of the phi function is: phi(n^m)=n^(m-1)*phi(n)
So phi(1000^2) = 1000*phi(1000).
So there is phi(1000) in the power tower and therefore the answer is 1 mod 1000

• Arghyadeep Chatterjee 4 months ago +1

Dude your concepts are very very unclear. Please revise and brush up basic number theory

• Benjamin Wang 4 months ago

Evyatar Baranga this might be wrong. Because power towers are computed from the top to the bottom. Hence, by the time you get to the “998^2” layer, it’s already not “1”

• Kevin Lu 4 months ago

The answer is 256.

Firstly, note that totient(n^2) = n * totient (n), which significantly speeds up the computations of the problems. This is not crucial to the solution, however, so the proof will be commented on this comment. Also, to compute the totient, the method demonstrated on AOPS was used (artofproblemsolving.com/wiki/index.php/Euler%27s_totient_function).

Let t(n) denote totient(n).
Let's first compute the first few values of t(n^2), for n >= 3.
t(3^2) = 6
t(4^2) = 8
t(5^2) = 20
Let s be t(3^2)^t(4^2)^t(5^2)...
To find the last three digits of s is equivalent to finding the least positive integer n such that s = n (mod 1000).
The Chinese remainder theorem will be used, so firstly the remainders upon division by 8 and 125 of s will be found.

Clearly, since 2 | 6, 8 | s, so the remainder upon dividing s by 8 is 0.
Secondly, Euler's totient theorem will be used to find the remainder upon division by 125 of s.
Let r be log(base 6)(s), so r is t(4^2)^t(5^2)...
Euler's totient theorem states that s mod 125 is equivalent to 6 ^ (r mod t(125)) = 6 ^ (r mod 100).
Similarly, the Chinese remainder theorem will be used to find r mod 100. Clearly, 4 | r. To find r mod 25 however, Euler's totient theorem has to be applied again. Note that r = 8 ^ 20 ^ ... and t(25) = 20, so r mod 25 = 8 ^ (20 mod t(25)) = 8 ^ (20 mod 20) = 8 ^ 0 = 1. Thus combining r = 0 mod 4 and r = 1 mod 25 yields r = 76 mod 100.
Therefore, s = 6 ^ 76 (mod 125). Note that 6 ^ 25 = 1 (mod 125), so s = 1 (mod 125). Combining this with s = 0 (mod 8) yields the only solution s = 256 (mod 1000). Thus, the answer is 256.

• Kevin Lu 4 months ago

I made a typo, s = 1 (mod 125) should be s = 6 (mod 125) in the last paragraph.

• Kevin Lu 4 months ago

Proof of t(n^2) = n*t(n).
Let the prime factors of n be p1,p2,p3...
Thus t(n^2) = n^2(1-1/p1)(1-1/p2)... = n (n(1-1/p1)(1-1/p2)...) = n*t(n).
QED

• Leo Lin 4 months ago +1

I'm not sure if my approach is acceptable, but I tackled this algorithmically. I implemented a simple brute force algorithm looping from 2019 to 3, and taking the phi( number ^2) and raising it to another, and after 1 hour of computing the final value was 2713536 which means that the last 3 digits are 536 (

• Benjamin Wang 4 months ago

Lolol and there’s no nice way to fix it becuz taking powers is not well behaved under mod

• Boris Valderrama 4 months ago

de result is like

• Leo Lin 4 months ago +2

just realized this is completely wrong because theres no humanly way my little macbook could compute such a large number, it turns out the program stopped computing after the first 2 iterations...

• Serengeti Ghasa 4 months ago

The answer is 376
Details would follow letter
With love

• NoName 4 months ago

let's hope the post office does delay the letter

• Minh Cong Nguyen 4 months ago +12

The answer is 256.

Let A= phi(3^2) ^ phi (4^2) ^ phi (5^2) ^.... then A = 6^(8^(20^N)), and we have to find the last 3 digits of A.

Obviously A = 0 (mod 8), we will show that A = 6 (mod 125).

We have 8^20 - 1 = 2^60-1 = (2^30-1)*(2^30+1) =(2^30-1)*(2^10+1)*(2^20+2^10+1) = (2^30-1)*1025*(2^20+2^10+1) = 0 (mod 25), then 8^20 = 1 (mod 25), therefore 8^(20^N) = 1 (mod 25)

We also have 6^25-1 = (6^5-1)*(6^20+6^15+6^10+6^5+1), and 6^5-1 = 7775 = 25*311, and 6^20+6^15+6^10+6^5+1 = 1+1+1+1+1 = 0 (mod5), therefore 6^25-1 = 0 mod 125, which means that 6^25=1 (mod 125)

Therefore, A = 6^(8^(20^N)) = 6^(25k+1) = 6*6^(25k) = 6*1 = 6 (mod 125).
Obviously A = 0 (mod 8) and A = 6 (mod 125), then A = 256 (mod 1000) and we are done.

• Mokou Fujiwara 4 months ago

Looks like it is same as my method.

• Karthasis 4 months ago

Perfect

• Sudheer Thunga 4 months ago

@Minh Cong Nguyen You are right Bro...like that power question...

• Anonimatus54125 4 months ago +1

@Minh Cong Nguyen Ok, thank you.

• Minh Cong Nguyen 4 months ago +1

@Anonimatus54125You can use Chinese remainder theorem to solve for A. Actually, some of the previous challenges in this channel have mentioned about this kind of problem.

• Jaleb 4 months ago +1

The answer is 256.
We must look at the order of each level of powers we go mod phi^(n) (1000) where n is the number of phi's are the number of powers above the base. By testing out each layer, we can find that 8^20k = 176 mod (400) for all k>1. After we've found this we get 6^8^20 = 256 mod 1000.

Note: the order of 20^k mod 160 is trivial as after k>3 it gives 20^k = 0 mod 160.

• LetsSolveMathProblems  4 months ago

@Jaleb I believe I am not familiar with the technique in which we look at "the highest power of 2 in the mod" then "find its own subgroup" to simplify modular exponentiation. Could you post a brief explanation on the technique? Also, is this technique viable without using a computer software?
*Edit: I will still recognize your solution since my lack of knowledge should not factor into which solution is acceptable.

• Mokou Fujiwara 4 months ago

I actually need Chinese Remainder Theorem to solve this.

• Jaleb 4 months ago

@LetsSolveMathProblemsI was using 20^3 = 160*n for the mod 400 powers.

Yes, the Totient formula doesn't give 1, but there is still a closed group of values after you reach a certain power which are the values of (2^i,160)=32 for i>=5. (Had a hard time finding the term which you get to the subgroup's identity). This order for this subgroup is 20.

I guess the thing I should have pointed out that once you reach the highest power of 2 in the mod you find its own subgroup. Might've been easier to break into the modulai of 125 and 8 for the solution. Then using CRT from there.

• LetsSolveMathProblems  4 months ago

I am having a hard time seeing how you calculated 8^20^k mod 400 for k >= 3. Note that we cannot directly apply Euler's Totient Formula to simplify the exponent (20^k) because 8 and 400 are not relatively prime. Furthermore, I believe the transition from 8^20^k = 176 mod 400 to 6^8^20 = 256 mod 1000 is not immediate, either.

• Minh Cong Nguyen 4 months ago

The answer is 256.

Let A= phi(3^2) ^ phi (4^2) ^ phi (5^2) ^.... then A = 6^(8^(20^N)), and we have to find the last 3 digits of A.

Obviously A = 0 (mod 8), we will show that A = 6 (mod 125).

We have 8^20 - 1 = 2^60-1 = (2^30-1)*(2^30+1) =(2^30-1)*(2^10+1)*(2^20+2^10+1) = (2^30-1)*1025*(2^20+2^10+1) = 0 (mod 25), then 8^20 = 1 (mod 25), therefore 8^(20^N) = 1 (mod 25)

We also have 6^25-1 = (6^5-1)*(6^20+6^15+6^10+6^5+1), and 6^5-1 = 7775 = 25*311, and 6^20+6^15+6^10+6^5+1 = 1+1+1+1+1 = 0 (mod5), therefore 6^25-1 = 0 mod 125, which means that 6^25=1 (mod 125)

Therefore, A = 6^(8^(20^N)) = 6^(25k+1) = 6*6^(25k) = 6*1 = 6 (mod 125).
Obviously A = 0 (mod 8) and A = 6 (mod 125), then A = 256 (mod 1000) and we are done.

• LetsSolveMathProblems  4 months ago

@Minh Cong Nguyen I usually disregard the obvious typos, so if you have a minor error, I encourage you to post the edit as a reply comment, but make no changes to the original comment. (No penalty will be given for evident typos.) I can consider only the first unedited comment you post in determining the order of recognition.

• Minh Cong Nguyen 4 months ago

I made a wrong typing, where A = 6^(4^(20^N)), which should be 6^(8^(20^N)), but the answer is still the same.

• Serengeti Ghasa 4 months ago +2

The answer is 125
⍉(3²)=5
⍉(4²)=7
⍉(5²)=19
let x=19ʷ which would be a odd number
y=7ˣ=(-1mod8)ˣ is -1mod8 if x is odd
5ʸ=5⁻¹ᵐ⁸
last 3 digit of5⁷ is 125 and 5⁸ is 625
so last three digit of 5⁸ˣ⁻¹=125×625ⁿ=125×625=125
with love
Prabhat Kumar Sahu
Singhijuba

• Serengeti Ghasa 4 months ago +1

Thanks for your kind information
Regards
Prabhat

• LetsSolveMathProblems  4 months ago +2

Note that phi(3^2) is 6, not 5, because 1 is relatively prime to any positive integer. (I am guessing you left out 1.)

• Nathan Farlow 4 months ago

The answer is 006
.

I wrote a python script that employed some math tricks to evaluate the result. The trick is to start with the topmost exponent and continually evaluate ans = (one exponent down) ^ ans until reaching phi(3^2). The phi function is easy for a computer to evaluate relatively quickly by checking if gcd(a, b) = 1. Now, the exponent tower gets huge very fast and much to large for my slow computer to try to evaluate. This can be solved by realizing that the last 3 digits of (a * b) is the same as the last 3 digits of (the last 3 digits of a multiplied by the last three digits of b). Using this optimization, we can evaluate (a ^ b) by (last 3 digits of a * last 3 digits of a * ... b times) applying the last 3 digits trick to each multiplication. This way, in a ^ b, we only multiply b 3 digit numbers (and we know that in our case b is also always not more than a 3 digit number). This causes the bottleneck to now be placed on the phi function, and I am confident that there are very easy ways to optimize this, however I was patient and let it run :) This took about 20 minutes on a single 2.8 ghz thread.

• Nathan Farlow 4 months ago

@LetsSolveMathProblems I gotcha I see where I went wrong. Looking forward to seeing this solution done the elegant mathematical way :)

• LetsSolveMathProblems  4 months ago

Note that the Euler's Totient Formula, which states that a^(phi(n)) = 1 mod n, applies only if *a and n are relatively prime*. This important condition may not be met as you progress up the exponent tower.

• Zemlya Drakona 4 months ago +2

1 is the answer.
I used the exponentially of the modulo function in repetition on Wolfram Alpha all the way to phi(10^2) to get (1^phi(11^2)^phi(12^2)...phi(2019^2))(mod 1000) equalling 1.

• Zemlya Drakona 4 months ago

(A^B)(mod C)=((A (mod C))^B)(mod C)

• Boris Valderrama 4 months ago

But this number is not computable, this is very big, it has trillion of numbers

• Benjamin Wang 4 months ago

Zemlya Drakona please note power towers are computed from the top to the bottom

• FloatingPotatoes 4 months ago +3

More than 6

• Pink Lady 4 months ago

Any more maths so complex like that, your computer will someday commit suicide.

• socerdemon8 4 months ago +1

256

• socerdemon8 4 months ago

@Mokou Fujiwara random guess

• Mokou Fujiwara 4 months ago

aided by calculator, right?

• SoW Lone Archer 4 months ago +5

Ehhh, I love you, saludos desde México. ❤

• Icestrike411 Cubing 4 months ago +2

owo