What is the remainder when 2^100 is divided by 7?
The remainder is 2. Since 2^3 = 8 leaves remainder 1 when divided by 7, 2^99 = (2^3)^33 also leaves 1, so 2^100 = 2^99 x 2 leaves 1 x 2 = 2.
Explain it simply
Remainders behave well under multiplication: the remainder of a product equals the remainder of the product of the remainders. So the trick is to find a small power that leaves remainder 1. Once you have it, that power is like a full lap around a running track: however many laps you run, you are back at the start, and only the leftover distance matters.
Example
Question: Find the remainder when 2^100 is divided by 7.
- Try small powers: 2^1 = 2, 2^2 = 4, 2^3 = 8. 8 / 7 leaves 1.
- Write 100 = 3 x 33 + 1, so 2^100 = (2^3)^33 x 2^1.
- (2^3)^33 leaves 1^33 = 1.
- So 2^100 leaves 1 x 2 = 2.
The remainders of powers of 2 by 7 cycle as 2, 4, 1, 2, 4, 1, ... and 100 is one more than a multiple of 3, so it takes the first value, 2.
let r = 1;
for (let i = 0; i < 100; i++) r = (r * 2) % 7;
console.log(r); // Output: 2What to say in the interview
"I look for a power of 2 that leaves remainder 1 when divided by 7. 2 cubed is 8, which does. 100 is 33 threes plus 1, so the answer is the remainder of 2 to the power 1, which is 2."
Common mistakes
- Computing 2^100 directly in a calculator, which loses precision and wastes time.
- Mixing up the leftover exponent: 100 mod 3 is 1, not 0.