2009 AMC 10B Problem 21

Since $3^2 = 9 \equiv 1 \pmod 8$, the powers of $3$ modulo $8$ alternate: even exponents give $1$, odd exponents give $3$.

The sum has exponents $0$ through $2009$, which is $2010$ terms. Group them into consecutive pairs $(3^{2k} + 3^{2k+1})$; each pair is $\equiv 1 + 3 = 4 \pmod 8$, and there are $1005$ pairs. The total is therefore
$$1005 \cdot 4 = 4020 \equiv 4 \pmod 8,$$
because $4020 = 8 \cdot 502 + 4$. Equivalently, $1005$ is odd, and an odd number of $4$'s is $4 \pmod 8$.

The answer is $\boxed{\textbf{(D)}\ 4}$.

Remainders of powers are periodic, and the period here is only $2$, so the whole sum reduces to counting blocks. Always count the number of terms carefully when the sum begins at exponent $0$. The parity of the number of blocks is what decides between $0$ and $4$.

Use the geometric series: the sum is $\frac{3^{2010} - 1}{2}$. Since $3^4 = 81 \equiv 1 \pmod{16}$ and $2010 = 4 \cdot 502 + 2$, we have $3^{2010} \equiv 9 \pmod{16}$, so $3^{2010} - 1 \equiv 8 \pmod{16}$ and dividing by $2$ gives $4 \pmod 8$.

• Counting 2009 terms instead of 2010 (the sum starts at the exponent 0), which leaves a stray term and gives remainder 1.
• Reducing the closed form $\frac{3^{2010}-1}{2}$ modulo $8$ directly; dividing by $2$ requires working modulo $16$ first.