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!

Repeated squaring mod 645

  1. Feb 28, 2013 #1
    1. The problem statement, all variables and given/known data
    Calculate [itex] 2^{644}[/itex] mod 645.


    2. Relevant equations

    I think I should use repeated squaring, but I'm open to other techniques.

    3. The attempt at a solution

    I start out fine,
    [tex] 2=2 \\
    2^2=4\\
    2^4= 16\\
    2^8=256\\
    2^{16}=65536\equiv 391 [/tex]
    But that's where it starts to break down. I don't think I understand the point of repeated squaring. I mean yes I know I am looking for 256+256+128+4 =644 but that requires calculating 2^256 mod 645, which is still stupidly difficult as far as I can tell, or is there something I'm missing?
     
  2. jcsd
  3. Feb 28, 2013 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That looks to me like some variation on Fermat's little theorem should work.
     
  4. Feb 28, 2013 #3
    Yeah.. Probably, but what?
     
  5. Feb 28, 2013 #4

    pasmith

    User Avatar
    Homework Helper

  6. Feb 28, 2013 #5

    rcgldr

    User Avatar
    Homework Helper

    If you're not going to use some special theorem, just continue, but then you run into a cyclic pattern at 2^28 because 2 is not a "primitive" of 645 (since 645 = 3 * 5 * 43, it isn't prime and I don't think there is a "primitive"):

    [tex]
    2^{16} | 645 = 391 \\
    2^{32} | 645 = 391^2 | 645 = 16 \\
    2^{28} | 645 = 1 \\
    2^{29} | 645 = 2 \\
    2^{30} | 645 = 4 \\
    2^{31} | 645 = 8 \\
    2^{32} | 645 = 16 \\
    2^{56} | 645 = 1 \\
    2^{n*28} | 645 = 1
    [/tex]
    For that last one, n can be any integer.
     
    Last edited: Feb 28, 2013
  7. Feb 28, 2013 #6

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Use the very most elementary property of 2 that you know.

    And I expect you know the binomial theorem.

    :wink:

    Then I think it is not too difficult.
     
  8. Feb 28, 2013 #7

    I like Serena

    User Avatar
    Homework Helper

    Hey Arcana!

    Euler's theorem says that ##a^{\phi(n)} \equiv 1 \pmod n## if a and n are relatively prime.
    Since 2 and 645 are relatively prime and ##\phi(645) = \phi(3 \cdot 5 \cdot 43) = (3-1) \cdot (5-1) \cdot (43-1) = 336##, we get that:
    $$2^{336} \equiv 1 \pmod {645}$$
    Can you use that to help simplify the expression?
    (If you have more problems like this, we'll soon get to the Chinese Remainder Theorem! :cool:)
     
  9. Feb 28, 2013 #8
    Thanks for all the help guys! I think rcgldr wins, with 2^28*n since I think I've used that kind of logic before. This doesn't really solve my question about the method of repeated squaring itself though, as 28 wouldn't have been in the sequence, but it wouldn't be the first time we learned a crappy method to calculate something (crappy by hand, cheaper by computer). I really don't like my number theory class..

    ILS, we did the Chinese remainder theorem on the last exam. :)

    What was epenguin implying about the binomial theorem?
     
  10. Feb 28, 2013 #9

    rcgldr

    User Avatar
    Homework Helper

    2^28 wouldn't have been in the repeated squaring sequence, but you eventually run into ((2^32) | 645)) = 16, indicating that the sequence had cycled, and if ((2^32) | 645)) = 16 = ((2^4) | 645)), then it would be expected for ((2^28) | 645)) = 1. For this case, ((2^((28*n) + m)) | 645)) = ((2^m) | 645)), where n and m are any integers.
     
    Last edited: Feb 28, 2013
  11. Mar 1, 2013 #10
    Thanks rcgldr, that's very helpful :)
     
  12. Mar 1, 2013 #11

    I like Serena

    User Avatar
    Homework Helper

    Aww, I really wanted to win!
    Although I have to admit that rcgldr, showing what the order of 2 is, did a good job. :wink:
     
  13. Mar 9, 2013 #12

    rcgldr

    User Avatar
    Homework Helper

    A late follow up on this, but instead of repeated squaring of 2 mod 645, it could be repeated squaring of 3 mod 929. 929 is a prime number, and 3 is a "primitive" of 929, and every number from 1 to 928 will end up being some power of 3 mod 929.

    The point of this is getting back to your original question, rather than calculaing 3^928 as a huge number, then taking the modulus of that huge number, you can perform all of the math modulo 929:

    3^0 mod 929 = 1
    3^1 mod 929 = 3
    3^2 mod 929 = 9
    3^4 mod 929 = 9^2 mod 929 = 81
    3^8 mod 929 = 81^2 mod 929 = 58
    3^16 mod 929 = 58^2 mod 929 = 577
    3^32 mod 929 = 577^2 mod 929 = 347
    3^64 mod 929 = 347^2 mod 929 = 568
    3^128 mod 929 = 568^2 mod 929 = 261
    3^256 mod 929 = 261^2 mod 929 = 304
    3^512 mod 929 = 304^2 mod 929 = 445
    3^768 mod 929 = 3^(512+256) mod 929 = 445 x 304 mod 929 = 575
    3^896 mod 929 = 3^(768+128) mod 929 = 575 x 261 mod 929 = 506
    3^928 mod 929 = 3^(896+32) mod 929 = 506 x 347 mod 929 = 1
     
    Last edited: Mar 9, 2013
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: Repeated squaring mod 645
  1. Repeated roots (Replies: 4)

  2. Mod-2 function? (Replies: 2)

Loading...