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

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:

usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

LetsSolveMathProblems4 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 Salhany4 months ago@LetsSolveMathProblems how old are you ?

Jonathan Liu4 months ago^{+1}Get well soon!

Mr L4 months ago@LetsSolveMathProblems yes, it's redundant!

LetsSolveMathProblems4 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 L4 months ago^{+2}Is it a^(b^c) or (a^b)^c?

Electro SchOOp4 months ago^{+2}The answer is between 0 and 999

Mokou Fujiwara4 months agoGood 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

Rafael4 months agoi 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 Araujo4 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

Karthasis4 months agoAnswer is 2^8

Midas Schonewille4 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 Nauli4 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 Nauli4 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 soum4 months ago@Nicolas Nauli why is 6^n congruent to 6 mod 10 ? im having a hard time

Nicolas Nauli4 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 Fujiwara4 months agoI 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 Nauli4 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 Chatterjee4 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 Ghasa4 months agoThe 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 Baranga4 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 Chatterjee4 months ago^{+1}Dude your concepts are very very unclear. Please revise and brush up basic number theory

Benjamin Wang4 months agoEvyatar 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 Lu4 months agoThe 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 Lu4 months agoI made a typo, s = 1 (mod 125) should be s = 6 (mod 125) in the last paragraph.

Kevin Lu4 months agoProof 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 Lin4 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 Wang4 months agoLolol and there’s no nice way to fix it becuz taking powers is not well behaved under mod

Boris Valderrama4 months agode result is like

Leo Lin4 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 Ghasa4 months agoThe answer is 376

Details would follow letter

With love

NoName4 months agolet's hope the post office does delay the letter

Minh Cong Nguyen4 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 Fujiwara4 months agoLooks like it is same as my method.

Karthasis4 months agoPerfect

Sudheer Thunga4 months ago@Minh Cong Nguyen You are right Bro...like that power question...

Anonimatus541254 months ago^{+1}@Minh Cong Nguyen Ok, thank you.

Minh Cong Nguyen4 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.

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

LetsSolveMathProblems4 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 Fujiwara4 months agoI actually need Chinese Remainder Theorem to solve this.

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

LetsSolveMathProblems4 months agoI 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 Nguyen4 months agoThe 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.

LetsSolveMathProblems4 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 Nguyen4 months agoI 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 Ghasa4 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 Ghasa4 months ago^{+1}Thanks for your kind information

Regards

Prabhat

LetsSolveMathProblems4 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 Farlow4 months agoThe 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 Farlow4 months ago@LetsSolveMathProblems I gotcha I see where I went wrong. Looking forward to seeing this solution done the elegant mathematical way :)

LetsSolveMathProblems4 months agoNote 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 Drakona4 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 Drakona4 months ago(A^B)(mod C)=((A (mod C))^B)(mod C)

Boris Valderrama4 months agoBut this number is not computable, this is very big, it has trillion of numbers

Benjamin Wang4 months agoZemlya Drakona please note power towers are computed from the top to the bottom

FloatingPotatoes4 months ago^{+3}More than 6

Pink Lady4 months agoAny more maths so complex like that, your computer will someday commit suicide.

socerdemon84 months ago^{+1}256

socerdemon84 months ago@Mokou Fujiwara random guess

Mokou Fujiwara4 months agoaided by calculator, right?

SoW Lone Archer4 months ago^{+5}Ehhh, I love you, saludos desde México. ❤

Icestrike411 Cubing4 months ago^{+2}owo