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!

Problem on exponents

  1. Oct 9, 2012 #1
    What will be the remainder when 2^256 is divided by 17 ?


    I tried expressing 2^256 as 16^64 and seeking a pattern between the remainders of the multiples of 16 when divided by 17 , but that didn't work
     
  2. jcsd
  3. Oct 9, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    Try converting 17 to base 2, and doing the divide in base 2 to look for a pattern, or convert to base 16 and divide in base 16. You'll need to convert back to decimal once you find a pattern.
     
  4. Oct 9, 2012 #3
    no luck
     
  5. Oct 9, 2012 #4

    uart

    User Avatar
    Science Advisor

    Some really useful properties of modulo.

    1. (a + b) mod q = ( (a mod q) + (b mod q) ) mod q

    2. (a b) mod q = ( (a mod q) (b mod q) ) mod q

    3. (b^a) mod q = ( (b mod q)^a ) mod q

    Note that for the last one you can take the modulo of the base (but not the exponent) before doing the exponentiation, without changing the final result. Use this to break your exponentiation down to a manageable size.

    So for example write [itex]2^{256} \mod 17 = (2^{16})^{16} \mod 17[/itex] and apply property (3) above.
     
  6. Oct 9, 2012 #5

    rcgldr

    User Avatar
    Homework Helper

    In base 16, you'd be dividing 100000... by 11. The quotient is F0F0F0... . In base 2 you'd be dividing 1000000.... by 10001, the quotient is 1111000011110000... . The remainder at each step also goes through a pattern.

    uart's modulo property #3 is also a good method and used in finite field math, but I don't know what you're expected to know at this point in your class.
     
    Last edited: Oct 9, 2012
  7. Oct 9, 2012 #6
    guys , i am in class 10th and i don't know any of these things . This question must have an easy but tricky solution .
     
  8. Oct 9, 2012 #7

    uart

    User Avatar
    Science Advisor

    That's ok, just read "modulo q" as "remainder when divided by q" and now it's year 10 level.

    2^16 modulo 17 = remainder when 2^16 is divided by 17. You can do that. :)
     
  9. Oct 9, 2012 #8

    rcgldr

    User Avatar
    Homework Helper

    The pattern method is similar to what uart is suggesting.

    what is

    2^8 mod 17
    2^16 mod 17
    2^24 mod 17
    2^32 mod 17
    ...
     
  10. Oct 10, 2012 #9
    so i would get , 16^64 mod 17 = ( ( 16 mod 17 )^64 ) mod 17

    how do i solve this ?
     
  11. Oct 10, 2012 #10

    rcgldr

    User Avatar
    Homework Helper

    Yes, but that doesn't help, since

    (16 mod 17) = 16

    try

    ( (16^2) mod 17) ^32) mod 17

    you can check this by trying

    ( (16^4) mod 17) ^16) mod 17

    or combining multiple rules:

    ( ( ((16^3) mod 17) ((16^3) mod 17) ((16^2) mod 17) )^8 ) mod 17

    you could also do this with powers of 2, notice a pattern (this is also what you would notice doing long division).

    (2^0 mod 17) = 1
    (2^1 mod 17) = 2
    (2^2 mod 17) = 4
    (2^3 mod 17) = 8
    (2^4 mod 17) = 16
    (2^5 mod 17) = 15
    (2^6 mod 17) = 13
    (2^7 mod 17) = 9
    (2^8 mod 17) = 1
    (2^9 mod 17) = 2
    ...

    I'm curious as to what you've been taught in the classroom, that would have helped solve this problem. Anything about remainders or modulo properties?
     
    Last edited: Oct 10, 2012
  12. Oct 12, 2012 #11
    it isnt a classroom problem , i am preparing for a scholarship 9 ( ntse ) and i found it in the sample papers :)
     
  13. Oct 12, 2012 #12

    rcgldr

    User Avatar
    Homework Helper

    Then the problem is probably based on how modulo works and the 3 rules posted by uart.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem on exponents
  1. Problem on exponent (Replies: 9)

Loading...