Official Solution:What is the remainder when you divide \(2^{200}\) by 7?
A. 1
B. 2
C. 3
D. 4
E. 5
We cannot compute \(2^{200}\) in anywhere near the time allotted, so we should look for a pattern in much simpler problems that we can scale up to \(2^{200}\).
The simpler problems we should solve are these:
What is the remainder when you divide 2 by 7?
What is the remainder when you divide \(2^2\) by 7?
What is the remainder when you divide \(2^3\) by 7?
What is the remainder when you divide \(2^4\) by 7?
... and so on with the powers of 2.
The answers follow this pattern:
2 divided by 7 leaves remainder 2.
\(2^2\) (which equals 4) divided by 7 leaves remainder 4.
\(2^3\) (which equals 8) divided by 7 leaves remainder 1.
\(2^4\) (which equals 16) divided by 7 leaves remainder 2.
\(2^5\) (which equals 32) divided by 7 leaves remainder 4.
\(2^6\) (which equals 64) divided by 7 leaves remainder 1.
We should stop as soon as we notice that the cycle will repeat itself forever in this pattern: [2, 4, 1]. Every third remainder is the same. (From here on out, "remainder" always means "remainder after we divide by 7.") Since every third remainder is the same, we should look at the remainder when the power is a multiple of 3. The remainders of 23 and 26 are 1. Thus, the remainder of 2 raised to a power that is any multiple of 3 is 1.
Now, 200 is not a multiple of 3, but we can look for a multiple of 3 near 200. 201 is a multiple of 3 (its digits add to 3), so \(2^{201}\) has a remainder of 1. Finally, we notice that the remainder of \(2^{200}\) must be one position earlier in the cycle than the remainder of \(2^{201}\). Since the cycle is [2, 4, 1], the remainder of \(2^{200}\) is 4.
Answer: D
_________________