To find the remainder when $a^n$ is divided by m:

Method: Write a = m*q + r (where r is a convenient small number). Then $a^n$ = (mq + r)^n. Expand using binomial theorem. All terms with m as a factor contribute 0 to the remainder. Only terms with pure powers of r matter.

Example: 7^{103} mod 25. Write 7 = 1 + 6, but 6^2 = 36 = 25 + 11 (messy). Better: 7^2 = 49 = 50 - 1. So 7^{103} = 7 * (7^2)^{51} = 7*(50-1)^{51}. Expanding: 7*[C(51,0)*50^{51} - C(51,1)50^{50} + ... - C(51,51)]. All terms except the last are divisible by 25 (contain factor 50). Last term: 7(-1) = -7 = 18 mod 25.