-1

I was wandering if there was a trick here that I'm not aware. For example (large number):

6612384^8

How can I apply mod 10?

Edward Chapman
  • 509
  • 6
  • 8
  • so you want the code? – B001ᛦ Oct 27 '15 at 12:41
  • 1
    I think this is a question is better to be put on math.stackexchange. Nevertheless, you got an answer. – Cristian Marian Oct 27 '15 at 12:46
  • Possible duplicate of [Calculating pow(a,b) mod n](http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – phuclv Oct 27 '15 at 13:29
  • If it's really a math question then it's off topic here. Duplicate: [How do I compute abmodcabmodc by hand?](http://math.stackexchange.com/q/81228/90333), [calculating abmodc](http://math.stackexchange.com/q/26722/90333) – phuclv Oct 27 '15 at 13:29
  • I'm voting to close this question as off-topic because it's about [math.se], not programming. – Pang Oct 28 '15 at 01:49

1 Answers1

3

modular exponentiation can be a lot more efficient then regular exponentiation. Taking advantage of the fact that a^b mod c == (a mod c)^b mod c, and using exponentiating by squaring,

6612384^8 mod 10 == 
4^8 mod 10 == 
16^4 mod 10 == 
6^4 mod 10 == 
36^2 mod 10 == 
6^2 mod 10 == 
36 mod 10 == 
6

All of which you could theoretically calculate even without a pen and paper.

Kevin
  • 74,910
  • 12
  • 133
  • 166
  • I'm sorry, I don't understand fully. I understand the rearrangement of the equation, but how do you get from '6612384^8 mod 10' to '4^8 mod 10'? Thanks for your help – Edward Chapman Oct 27 '15 at 13:07
  • `a^b mod c == (a mod c)^b mod c`, so `6612384^8 mod 10 == (6612384 mod 10)^8 mod 10 == 4^8 mod 10. – Kevin Oct 27 '15 at 13:13
  • But does 4^8 mod 10 equal 6612384^8 mod 10? What if the modulus was 11 for example? – Edward Chapman Oct 27 '15 at 13:16
  • "But does 4^8 mod 10 equal 6612384^8 mod 10?". Yes, and 4^8 mod 10 equals 9994^8 mod 10, which equals 12345674^8 mod 10. "What if the modulus was 11 for example?". That's a little harder. calculating a big number mod 10 is very easy since it's always equal to the rightmost digit. This isn't the case for mod 11 or any other number. You would need to do long division on `6612384/11` and find the remainder. Or use the "%" button on a calculator. – Kevin Oct 27 '15 at 13:21