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 of 2^999

  1. Oct 11, 2007 #1
    I was trying to find last two digits of 2^999
    I proceeded like this
    2=2 (mod 100)
    2^2=2*2=4(mod 100)
    2^4=4*4=16 (mod 100)
    2^8=16*16=256=56 (mod 100)
    2^16=56*56=3136=36 (mod 100)
    2^32=36*36=96 = -4 (mod 100)
    2^64=-4*-4 =16 (mod 100)
    2^128=16*16=56 (mod 100)
    2^256=56*56=36 (mod 100)
    2^512=36*36=-4 (mod 100)

    Therefore 2^999= 2^512 * 2^256 * 2^128 * 2^64 * 2^32 * 2^4 *2^2 * 2^1 (mod 100)

    =-4*36*56*16*-4*16*4*2 (mod 100)
    = 66060288
    =88 (mod 100)
    Problem is this if reduce 2^999 mod 25 I get
    2^1 = 2 mod(25)
    2^2 =4 mod(25)
    2^4 =16 mod(25)
    2^8 =6 mod(25)
    2^16 =11 mod(25)
    2^32 =21 mod(25)
    2^64 =16 mod(25)
    2^128 =6 mod(25)
    2^256 =11 mod(25)
    2^512 =21 mod(25)

    2^999 = 21*11*6*16*21*16*4*2 (mod 25)=59609088
    If I take remainder of 59609088/100 i get the same result as before.
    Why does this work?That is I can reduce 2^999 mod 25 and take reminder of last number I obtain divided by 100
    Again is there a simpler way of doing it?
    I cannot use Euler as 2 and 100 are not co prime.
     
  2. jcsd
  3. Oct 11, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It is just a coincidence - you have arbitrarily reduced things mod 25 and 100 when it suits you, and not consistently with regards to choices of remainders. Why did you use 21 and not -4, when you used -4 and not 96? (And if you still don't believe it was fluke, then evaluate 30^1 mod 100 and mod 25 to see you don't get the same things).


    Assuming everything is random, there was a one in 4 chance of this happening. 2^999 is 13 mod 25, thus if we pick some thing at random that is 13 mod 25, then there is a 1 in 4 chance it was 88 mod 100.
     
    Last edited: Oct 11, 2007
  4. Oct 11, 2007 #3
    Thanks a lot matt
    Here's why I tried 25.
    While I took all the pain to evaluate remainders of powers of 2.
    A brainier guy suggested this.

    2^999 = ((2^10)^99)*(2^9)

    Now 2^10 =1024 = -1 (mod 25)
    and 2^9=512=12 (mod 25)
    2^299=-1*12=-12=13 (mod 25)

    Now he suggested this
    13 (mod 25) could be any of 13 or 13+25 or 13+50 or 13+75 (mod 100)
    or any of 13,38,63,88 .(As you have already observed in your post)
    And since 2^999 is exactly divisible by 4
    Only choice could be 88
    There is only one problem.How did he arrive at 25????????
    That's where I always get stumped.
    Somebody always has an elegant solution to things I work out the hard way...
     
  5. Oct 11, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Well, why not 25?

    Have you heard of the chinese remainder theorem? That might tell you what you need to know....
     
  6. Oct 11, 2007 #5
    You already noted that 100 has powers of 2 in it which precludes using Euler, so divide 100 by 4 to get a mod that can be evaluated using Euler and used the fact that the result mod 100 must be divisible by 4.
     
  7. Oct 11, 2007 #6
    Yes I have heard of it.
    It says that I can solve a series of modular equations provided moduli are prime to each other .The solution is unique to LCM of moduli.
    But how do I arrive at conclusion that 25 is possible candidate??
     
  8. Oct 11, 2007 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Let's think about this: the C.R.T. says that if I have X mod A and X mod B, where A and B are coprime, then I can find X mod AB. Now, I don't believe you cannot see how 100, 25 and 4 relate to A, B and AB.
     
  9. Oct 11, 2007 #8
    I got it thanks...
     
  10. Oct 11, 2007 #9
    I threw a few numbers out of the calculator, and noticed that 3^20 = 1 (mod 100).
    Since 2^10 = 1024 = 2*3 . 3 (mod 100),
    I found easier to use these two facts to reduce bigger powers to smaller ones.

    In what follows, every time you see a 2^10, you can replace it by 2^3 . 3; and when you see a 2^30 (or a power of it), it can simply vanish.

    Starting with 2^1000, you have
    2^1000 = (2^3 . 3) ^ 100 = 2^300 . 3^100 = 2^300 (mod 100)
    2^300 = (2^3 . 3) ^ 30 = 2^90 . 3^30 = (2^3 . 3) ^ 9 . 3^20 . 3^10 = 2^27 . 3^19 (mod 100)
    Now
    2^27 . 3^19 = 2^7 . (2^3 . 3) ^ 2 . 3^20 / 3 = 2^7 . 2^6 . 3^2 / 3 = 2^13 . 3 (mod 100)
    So
    2^999 = 2^1000 / 2 = 2^12 . 3 = 96 . 3 = 88 (mod 100)
     
  11. Oct 22, 2007 #10
    100 = 4 * 25, gcd(4, 25) = 1, so [tex]\phi(100)=40[/tex] and [tex]4^{40n+k}\equiv4^{k}(mod 100)[/tex].
    [tex]2^{999}\equiv2*4^{499}\equiv2*4^{40*12+19}\equiv2*4^{19}\equiv2^{39}\equiv2^{10}2^{10}2^{10}2^{9}\equiv24*24*24*12\equiv88(mod 100)[/tex]
     
  12. Oct 22, 2007 #11
    Why [tex]4^{40n+k}\equiv4^{k}(mod\ 100)[/tex]? this question is the same question as why the remainder of [tex]2^{999}[/tex] modulo 100 equals the remainder of [tex]2^{999}[/tex] modulo 25.
    let m = pq with gcd(p, q) = 1, then [tex]\phi(m)=\phi(p)*\phi(q)[/tex], let a is divisible by p and not by q, then gcd(a, q) = 1, according to Euler's Formula, we can get [tex]a^{n\phi(m)+k}\equiv a^{n\phi(p)\phi(q)+k}\equiv a^{k}(mod\ q)[/tex], then [tex]a^{n\phi(m)+k}-a^{k}[/tex] is divisible by q, since a is divisible by p, we also have [tex]a^{n\phi(m)+k}-a^{k}[/tex] is divisible by p, since gcd(p, q) = 1, we get [tex]pq|a^{n\phi(m)+k}-a^{k}[/tex], in orther words [tex]a^{n\phi(m)+k}\equiv a^{k}(mod\ m)[/tex]
     
    Last edited: Oct 22, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?