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:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 65

  • LetsSolveMathProblems

    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
      Patrick Salhany Month ago

      @LetsSolveMathProblems how old are you ?

    • Jonathan Liu
      Jonathan Liu Month ago +1

      Get well soon!

    • Mr L
      Mr L Month ago

      @LetsSolveMathProblems yes, it's redundant!

    • LetsSolveMathProblems
      LetsSolveMathProblems  Month 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
      Mr L Month ago +2

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

  • Electro SchOOp
    Electro SchOOp Month ago +2

    The answer is between 0 and 999

  • Mokou Fujiwara
    Mokou Fujiwara Month 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
    Rafael Month 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
      Jaime Araujo Month 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
    Karthasis Month ago

    Answer is 2^8

  • Midas Schonewille
    Midas Schonewille Month 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
    Nicolas Nauli Month 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
      Nicolas Nauli Month 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
      Sam soum Month ago

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

    • Nicolas Nauli
      Nicolas Nauli Month 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
      Mokou Fujiwara Month 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
      Nicolas Nauli Month 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
    Arghyadeep Chatterjee Month 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
    Serengeti Ghasa Month 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
    Evyatar Baranga Month 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
      Arghyadeep Chatterjee Month ago +1

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

    • Benjamin Wang
      Benjamin Wang Month 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
    Kevin Lu Month 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
      Kevin Lu Month ago

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

    • Kevin Lu
      Kevin Lu Month 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
    Leo Lin Month 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
      Benjamin Wang Month ago

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

    • Boris Valderrama
      Boris Valderrama Month ago

      de result is like

    • Leo Lin
      Leo Lin Month 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
    Serengeti Ghasa Month ago

    The answer is 376
    Details would follow letter
    With love

    • NoName
      NoName Month ago

      let's hope the post office does delay the letter

  • Minh Cong Nguyen
    Minh Cong Nguyen Month 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
      Mokou Fujiwara Month ago

      Looks like it is same as my method.

    • Karthasis
      Karthasis Month ago

      Perfect

    • Sudheer Thunga
      Sudheer Thunga Month ago

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

    • Anonimatus54125
      Anonimatus54125 Month ago +1

      @Minh Cong Nguyen Ok, thank you.

    • Minh Cong Nguyen
      Minh Cong Nguyen Month 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
    Jaleb Month 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
      LetsSolveMathProblems  Month 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
      Mokou Fujiwara Month ago

      I actually need Chinese Remainder Theorem to solve this.

    • Jaleb
      Jaleb Month 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
      LetsSolveMathProblems  Month 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
    Minh Cong Nguyen Month 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
      LetsSolveMathProblems  Month 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
      Minh Cong Nguyen Month 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
    Serengeti Ghasa Month 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
      Serengeti Ghasa Month ago +1

      Thanks for your kind information
      Regards
      Prabhat

    • LetsSolveMathProblems
      LetsSolveMathProblems  Month 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
    Nathan Farlow Month 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
      Nathan Farlow Month ago

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

    • LetsSolveMathProblems
      LetsSolveMathProblems  Month 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
    Zemlya Drakona Month 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
      Zemlya Drakona Month ago

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

    • Boris Valderrama
      Boris Valderrama Month ago

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

    • Benjamin Wang
      Benjamin Wang Month ago

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

  • FloatingPotatoes
    FloatingPotatoes Month ago +3

    More than 6

  • Pink Lady
    Pink Lady Month ago

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

  • socerdemon8
    socerdemon8 Month ago +1

    256

  • SoW Lone Archer
    SoW Lone Archer Month ago +5

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

  • Icestrike411 Official
    Icestrike411 Official Month ago +2

    owo