KA-0169Remainders and modular cycles
3 points, difficulty 1 of 3Level 11–12about 90sWhat is the remainder when 7 to the power 100 is divided by 5?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Replace 7 by its remainder on division by 5 before doing anything else.
2The strategy
7 leaves 2, so 7^100 leaves the same remainder as 2^100. Now find the cycle of 2 modulo 5.
3The full solution
2, 4, 3, 1 repeats with length 4, and 100 is a multiple of 4, so the remainder is the last entry: 1.
Solution
The reliable way
First reduce the base: 7 leaves remainder 2 on division by 5, so 7^100 and 2^100 leave the same remainder. Now find the cycle of powers of 2 modulo 5: 2, 4, 8 -> 3, 16 -> 1, and then it repeats. The cycle is 2, 4, 3, 1 with length 4. Since 100 = 4 x 25 is an exact multiple of 4, the exponent lands on the LAST entry of the cycle, giving remainder 1. The transferable idea: reduce the base first, then find the cycle length, then locate the exponent within it.
The elegant way
2^4 = 16 leaves 1, so 2^100 = (2^4)^25 leaves 1^25 = 1.
Why this is on the test: Reducing the base before finding the cycle is what keeps these arithmetic-free, and an exact multiple landing on the last entry is the usual off-by-one.