Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Remainders of large powers can be found by looking for the point where the remainders start to repeat.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Find where the powers return to , then reduce the exponent by that cycle length.
(a) and . Since , we get .
(b) Powers of modulo : , , , . So the cycle has length . Now , so , and .
(c) Powers of modulo return to first at , and no earlier. Any such must divide , the cycle length for modulus , and by direct multiplication.
(d) Modulo the powers of return to exactly when . There are such .
(e) , so . Also and , so . The sum is .
Check. Computing each remainder from the whole power by repeated squaring, and the powers for every up to , gives the same numbers.
Log in to join the discussion.
Loading…