1. Limited time only! Sign up for a free 30min personal 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!

Hex number exponentiation - modulo

  1. Oct 18, 2011 #1
    I have a hexadecimal number: 0x83

    I need to determine 0x83^11 mod 15. Where the 11 and 15 are decimal.

    I figured 0x83 = 131 decimal.

    131^11 = 194977389846841709335931.

    194977389846841709335931 mod 15 = 11

    11 = 0x0b

    Does that seem right?
     
  2. jcsd
  3. Oct 18, 2011 #2
    That's right, but you can get there more easily. In fact you can do it in your head.

    Recognize that 131 = 11 mod 15.
    So 131^2 mod 15 = 11^2 mod 15. But 11^2 = 1 mod 15.
    Since 131^10 = (131^2)^5, you know that 131^10 = 1 mod 15.
    Finally, 131*(131^10) = 11*1 mod 15 = 11.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook