
Modular arithmetic
Can someone explain why this works?
5^101 mod 124 = 5^(101 mod 3) mod 124 = 5^2 mod 124 = 25
How did they know to choose 3 in the problem above? If given a problem like this, I don't see how I would deduce that I need to take 101 mod 3 to make the problem easier.
Thanks
Edit: Is there a general formula for this? Can I use this in any problem with a large exponent?

Re: Modular arithmetic
note that 5^{3} = 125 = 1 (mod 124).
so if n = 3k + t (that is: n = t (mod 3))
5^{n} = (5^{3k})(5^{t}) = (5^{3})^{k}(5^{t}) = (1^{k})(5^{t}) = 5^{t} (mod 124).