1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Last two digits mod 100 problem

  1. May 29, 2017 #1
    1. The problem statement, all variables and given/known data
    upload_2017-5-29_21-33-4.png
    the question requires you to find the last two digits of x

    2. Relevant equations
    φ(n) = n * (Σ (1 - 1/p) ) where p are the distinct prime factors of n the totient function

    gcd(a ,n) = 1

    aφ(n)≡ 1 mod n

    3. The attempt at a solution
    typically this kind on question i would solve it like say

    1940 ≡ 1 mod(100)

    but here the exponent is not a simple multiple of 40 or near multiples of 40 then how am i supposed to do this
     
  2. jcsd
  3. May 29, 2017 #2

    rcgldr

    User Avatar
    Homework Helper

    What is the order of evaluation, right to left or left to right? Either way, the problem could be solved with a program that uses repeated squaring to raise a number to a power modulo 100.
     
  4. May 29, 2017 #3
    um this is olympaid question with no calculator
     
  5. May 30, 2017 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I would start at the bottom. What can you do with 19k mod 100?
     
  6. May 30, 2017 #5
    While studying the repetition period of the powers is a possible method, it can still get rather tedious (especially if you need to do it by hand in a time limited situation).

    Another method is to try considering ##19 = (20-1)## and performing a binomial expansion of the expression. The modulo arithmetic kills off most of the terms in the expansion.
    [Subsequent hint is to next decompose ##17 = \left(15 + 2 \right)##.]
     
  7. May 31, 2017 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that's what I was hinting at in post #4.

    Also, I suggest a convenient notation will make the writing out easier. I wrote @19=19@17, etc., and used % for modulo. Thus, the question is expressed as @19%100 (@ takes precedence over %).
     
  8. May 31, 2017 #7
    Ah okay, I was wondering whether you meant that or to look for the repetition cycles (the latter of which I actually tried, and its, well, not that bad I guess).
     
  9. May 31, 2017 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Fair enough.
     
  10. May 31, 2017 #9
    @haruspex
    19k mod 100 oscillates between 9 and 1 depending on whether k is odd or even respectively
     
  11. May 31, 2017 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, that would be mod 10. Use @Fightfish's stronger hint, the binomial expansion of (20-1)k.
     
  12. May 31, 2017 #11
    well
    202 ≡ 0 mod 100
    subsequently for n ≥2
    20n ≡0 mod 100

    then only the last two terms in the binomial expansion survive
    (20 -1)k mod 100= k (20) (-1)k-1 + (-1)k mod 100
    since k is odd here

    19k ≡ 20k -1 mod 100

    then how to proceed if this is correct
     
  13. May 31, 2017 #12

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Starting with the first power, k=17, that is, 1917=20*17-1 mod 100. Now raise it to the 15th power. (hint: 17=20-3).
     
    Last edited: May 31, 2017
  14. May 31, 2017 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No. It is 19(17(15..., not ((1917)15...)
     
  15. May 31, 2017 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Right, so using my notation we have @19%100=(20@17-1)%100=20@17%100-1 (yes?).
    Can you take the 20 out as a factor, i.e. write 20k mod 100 (=20@17%100) as 20(some expression)?
     
  16. Jun 4, 2017 #15

    ehild

    User Avatar
    Homework Helper
    Gold Member

    [tex]17^{15^{13^{11^{9^{7^{5^{3^{1}}}}}}}}=17^M[/tex], the right side is 19 on some power of 17.
    You got ##19^k=20k-1##. For k=17, ##19^k=20*17-1##. Following @haruspex's hint write 17=20-3 , so 1917=20*(20-3) - 1 = - 61 mod 100 or 39 mod 100. Raise 39 mod 100 to the 17th power again, and again, and find the period of the repetition cycle.
     
  17. Jun 5, 2017 #16

    sorry for the late reply in overseas

    19@17 ≡ 20@17 -1 mod 100

    isn't 20@17 mod 100 ≡0
    then isn't 20@17 -1 mod 100 ≡ -1
    what is happening?
     
  18. Jun 5, 2017 #17
    can some one explain to me because i kind of dont understand what i myself am doing

    19k ≡ 20k -1 mod 100
    this means when 19k is divided by 100 you get 20k -1 as remainder

    but 20 k -1 can be bigger than hundred itself
    so once again taking mod 100
    since k = @17 bigger than 2
    202≡ 0 mod 100

    20k -1 mod 100 ≡ -1 mod 100
    i am doing something terribly wrong what is it? point out to me?
     
  19. Jun 5, 2017 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No. Perhaps my notation is too confusing. 20@17 stands for 20 times @17, i.e. 20 times 171513..., not 20@17.
     
  20. Jun 5, 2017 #19

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Power is not product. If k is odd, 203=0 mod 100, but 20*3=60 mod 100, 20*5=0 mod 100, 20*7 =40 mod 100....
     
  21. Jun 5, 2017 #20
    oh ya sorry i got confused with power and product there i reworked tell me if this correct thanks

    so
    19k ≡ 20k -1 mod 100

    19@17 ≡ 20 @17 -1 mod 100

    20@17 -1 mod 100 = 20@(20-3) -1 mod 100

    20@(20-3) - 1 = 20 * (20 -3)m -1 where m is a positive integer

    so every term but the last term in the binomial is killed because it has at least a 202 term in it the remaining modulo congruence can be written as

    20*(-3)@15 -1 mod 100
    now since 20 * k mod 100 has a repetition of 5 we only need to consider (-3)@15 mod 5

    this is a cycle of
    -3 , 4 ,-2 , 1 or 2,4,3,1

    now we need to find @15 mod 4 = 15@13 mod 4 = (16 - 1)@13 mod 4 ≡ (-1) @13 mod 4

    now since @13 is odd it gives a remainder of -1 or 3

    so @15 mod4 ≡ 3
    so 20(3) -1 to give a final remainder of 59 mod 100
    is this correct?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Last two digits mod 100 problem
Loading...