What is remainder when 5 to the power of 30 is divided by 7?
Look at the powers of 5 mod 7:
5¹ mod 7 = 5
5² mod 7 = 5 × (5¹ mod 7) mod 7 = (5 × 5) mode 7 = 25 mod 7 =
4
5³ mod 7 = 5 × (5² mod 7) mod 7 = (5 × 4) mod 7 = 20 mod 7 =
6
5⁴ mod 7 = 5 × (5³ mod 7) mod 7 = (5 × 6) mod 7 = 30 mod 7 =
2
5⁵ mod 7 = 5 × (5⁴ mod 7) mod 7 = (5 × 2) mod 7 = 10 mod 7 =
3
5⁶ mod 7 = 5 × (5⁵ mod 7) mod 7 = (5 × 3) mod 7 = 15 mod 7 =
1
5⁷ mod 7 = 5 × (5⁶ mod 7) mod 7 = (5 × 1) mod 7 = 5 mod 7 =
5
At this point, it is obvious that the remainders will repeat the
cycle {5, 4, 6, 2, 3, 1}
There are 6 remainders in the cycle, so the remainder of 30
divided by 6 will tell you which remainder to use; if the remainder
is 0, use the 6th element.
30 ÷ 6 = 5 r 0 →use the 6th element which is 1, so 5³⁰ ÷ 7 will
have a remainder of 1.
1 ≡ 5³⁰ mod 7.