AMC 10 · 2009 · #21
Grade 4 number-theoryWhat is the remainder when 30+31+32+⋯+32009 is divided by 8?
Pick an answer.
AMC 10 2009 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Add up the powers of $3$ from $3^0$ all the way to $3^{2009}$, then divide that giant total by $8$. Find the remainder.
Givens: The sum is $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$; The exponents run from $0$ to $2009$, so there are $2010$ terms; We divide the whole sum by $8$
Unknowns: The remainder when the sum is divided by $8$
Understand
Restated: Add up the powers of $3$ from $3^0$ all the way to $3^{2009}$, then divide that giant total by $8$. Find the remainder.
Givens: The sum is $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$; The exponents run from $0$ to $2009$, so there are $2010$ terms; We divide the whole sum by $8$
Plan
Primary tool: #5 Look for a Pattern
Secondary: #9 Solve an Easier Related Problem, #7 Identify Subproblems, #3 Eliminate Possibilities
The sum is far too big to add up, so Tool #9 (Solve an Easier Related Problem) shrinks it: the remainder of a sum divided by $8$ depends only on the remainders of the parts, so replace each power $3^k$ by its small remainder. Tool #5 (Look for a Pattern) is the engine: the remainders of $3^0,3^1,3^2,\ldots$ do not grow, they loop in a short cycle, so we never touch the huge numbers. Tool #7 (Identify Subproblems) turns "add $2010$ remainders" into the easy sub-task of pairing them, and Tool #3 (Eliminate Possibilities) matches the final remainder to one of the five listed choices.
Execute — Answer: D
4.OA.C.5 Step 1 Find the remainder cycle
- List the remainders of the powers of $3$ when divided by $8$.
- $3^0=1$ leaves $1$.
- $3^1=3$ leaves $3$.
- $3^2=9=8+1$ leaves $1$.
- $3^3=27=24+3$ leaves $3$.
- Because $3^2$ is back to remainder $1$, every following power just repeats: the remainders march $1,3,1,3,1,3,\ldots$ forever, a cycle of length $2$.
- Even exponents leave $1$; odd exponents leave $3$.
💡 Once a remainder repeats, the whole list loops, so you only need the short cycle, not the giant powers.
3.OA.B.5 Step 2 Swap each power for its remainder
- The remainder of a sum divided by $8$ is fixed by the remainders of its pieces: add the small remainders, then take that total's remainder.
- So instead of the real sum, add up its remainders $1+3+1+3+\cdots$, one entry for each of the $2010$ terms.
- This is a legal move because addition can be regrouped and reordered without changing the remainder.
💡 Remainders add just like the numbers do, so the messy sum and the tidy remainder sum leave the same leftover.
4.NBT.B.5 Step 3 Pair them and total
- Group the remainders two at a time: $(1+3)$, then $(1+3)$, and so on.
- Each pair adds to $4$.
- There are $2010$ terms, which is $2010\div 2 = 1005$ pairs.
- So the whole remainder sum is $1005$ copies of $4$, that is $1005\times 4 = 4020$.
💡 Bundling the loop into equal pairs turns a long addition into one multiplication.
4.NBT.B.6 Step 4 Divide and match the choice
- Now divide the tidy total by $8$: $4020 = 8\times 502 + 4$, since $8\times 502 = 4016$ and $4020-4016 = 4$.
- The leftover is $4$, so the original giant sum also leaves remainder $4$ when divided by $8$.
- Among the choices $0,1,2,4,6$, that is $\textbf{(D)}\ 4$.
💡 The remainder of the small stand-in total is the remainder of the real sum, so one short division finishes it.
4.OA.C.5 List the remainders of the powers of $3$ when divided by $8$. $3^0=1$ leaves $1$ 3.OA.B.5 The remainder of a sum divided by $8$ is fixed by the remainders of its pieces: 4.NBT.B.5 Group the remainders two at a time: $(1+3)$, then $(1+3)$, and so on. Each pair 4.NBT.B.6 Now divide the tidy total by $8$: $4020 = 8\times 502 + 4$, since $8\times 502 = Review
Reasonableness: The remainder $4$ is between $0$ and $7$, as any remainder mod $8$ must be, and it matches a listed choice. A quick sanity check on a short version: $3^0+3^1+3^2+3^3 = 1+3+9+27 = 40 = 8\times 5$, remainder $0$, which agrees with pairing (two pairs each worth $4$ give $8$, remainder $0$). Adding two more terms $3^4+3^5$ contributes remainders $1+3=4$, matching our $2010$-term count that ends on one extra pair worth $4$.
Alternative: Group in fours instead of twos: any four consecutive powers sum to $3^k(1+3+9+27)=3^k\cdot 40$, and $40$ is divisible by $8$, so each block of four leaves remainder $0$. The $2010$ terms split into $502$ full blocks ($2008$ terms) plus the leftover $3^{2008}+3^{2009}$, whose remainders are $1+3=4$. So the answer is again $\textbf{(D)}\ 4$.
CCSS standards used (min grade 4)
4.OA.C.5Generate a number or shape pattern following a given rule (Building the repeating remainder cycle $1,3,1,3,\ldots$ of the powers of $3$ divided by $8$.)3.OA.B.5Apply properties of operations as strategies to multiply and divide (Justifying that the remainders may be added and regrouped, so the sum and the sum of remainders leave the same remainder.)4.NBT.B.5Multiply a whole number of up to four digits by a one-digit whole number (Turning $1005$ equal pairs of value $4$ into the single product $1005\times 4 = 4020$.)4.NBT.B.6Find whole-number quotients and remainders with up to four-digit dividends (Dividing $4020$ by $8$ to read off the remainder $4$.)
⭐ Powers of $3$ leave remainders that loop $1,3,1,3$ when divided by $8$; pair them up, and $1005$ pairs of $4$ leave remainder $4$ — choice $\textbf{(D)}$.
⭐ Powers of $3$ leave remainders that loop $1,3,1,3$ when divided by $8$; pair them up, and $1005$ pairs of $4$ leave remainder $4$ — choice $\textbf{(D)}$.
More like this
Same archetype — closest grade level first.