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