2009 AMC 10B Problem 21

The numbers are huge, but only their remainders when divided by $8$ matter. Start with the first few powers of $3$ and look for a pattern.

1. List the first few powers and their remainders:

1. The remainders repeat $1, 3, 1, 3, \ldots$ The reason: multiplying by $9$ (that is, by $3$ twice) leaves the remainder unchanged, because $9$ is $8 + 1$.
2. Count the terms. The exponents go from $0$ to $2009$, so there are $2010$ terms.
3. Group them in pairs: $(3^0 + 3^1) + (3^2 + 3^3) + \cdots + (3^{2008} + 3^{2009})$. That is $2010 \div 2 = 1005$ pairs.
4. Each pair has remainders $1 + 3 = 4$.
5. So the whole sum has the same remainder as $1005 \times 4 = 4020$. Since $4020 = 8 \times 502 + 4$, the remainder is $4$.
6. A quicker way to see step 6: two $4$'s make $8$, which leaves remainder $0$. So $1005$ fours leave the same remainder as one $4$, because $1005$ is odd.

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

Remainders of powers always repeat after a while, and here they repeat every $2$ steps. That lets you replace a giant sum by a count of repeating blocks. Be careful counting terms when the exponents start at $0$: from $0$ to $2009$ is $2010$ terms, not $2009$.

The sum is a geometric series, equal to $\frac{3^{2010} - 1}{2}$. Look at remainders when dividing by $16$ (we will divide by $2$ at the end): $3^4 = 81 = 5 \times 16 + 1$, so powers of $3$ repeat every $4$ steps when divided by $16$. Since $2010 = 4 \times 502 + 2$, $3^{2010}$ has the same remainder as $3^2 = 9$. So $3^{2010} - 1$ leaves remainder $8$ when divided by $16$, which means it equals $16k + 8$ for some whole number $k$. Halving gives $8k + 4$, remainder $4$.

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}$.