KA-0161Remainders and modular cycles
3 points, difficulty 1 of 3Level 9–10about 75sWhat is the remainder when 2 to the power 50 is divided by 7?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Work out the remainders of the first few powers of 2 when divided by 7.
2The strategy
2, 4, 8, 16, 32, 64 leave 2, 4, 1, 2, 4, 1 - the remainders cycle with length 3.
3The full solution
50 divided by 3 leaves remainder 2, so 2^50 leaves the same remainder as 2^2, which is 4.
Solution
The reliable way
Powers repeat their remainders. Dividing by 7: 2^1 leaves 2, 2^2 leaves 4, 2^3 = 8 leaves 1, and then the pattern restarts because multiplying by 2 again gives 2. So the cycle is 2, 4, 1 with length 3. Now 50 = 3 x 16 + 2, so 2^50 sits in the same place as 2^2 and leaves remainder 4. The transferable idea: find the first exponent that returns a remainder of 1, and the cycle length is that exponent.
The elegant way
2^3 leaves 1, so 2^48 leaves 1, and two more doublings give 4.
Why this is on the test: Modular cycles turn an impossible calculation into a division you can do in your head.