KA-0053Remainders and modular cycles
4 points, difficulty 2 of 3Level 5–6about 105sWhat is the remainder when 2 to the power 30 is divided by 7?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Work out the first few powers and their remainders.
2The strategy
Remainders of powers repeat on a short cycle. Find the remainders of 2, 4, 8, 16 and so on when divided by 7, and stop as soon as the list starts repeating.
3The full solution
The remainders go 2, 4, 1, then 2, 4, 1 again - a cycle of length 3. Since 30 is a multiple of 3, the answer is the last of the cycle, which is 1.
Solution
The reliable way
Build the cycle of remainders. 2 leaves 2, 4 leaves 4, 8 leaves 1, 16 leaves 2, 32 leaves 4, 64 leaves 1 - so the remainders repeat every 3 powers as 2, 4, 1. Because 30 divides exactly by 3, the thirtieth power sits at the end of a full cycle, giving remainder 1. The transferable idea: a remainder of zero lands on the last entry of the cycle, not the first.
The elegant way
2 cubed is 8, which is one more than 7, so 2 to the power 30 is (2 cubed) to the power 10, which leaves the same remainder as 1 to the power 10 - namely 1.
Why this is on the test: It is the remainder cycle again with a bigger modulus, and the remainder-of-zero edge case is exactly where students slip.