AMC 10 · 2021 · #10

Grade 8 number-theory
Archetype Modular Cycle Frequency Count └ Sub-archetype Power-Cycle Residue
base-conversionmodular-arithmeticplace-valueexponents easier-related-problempattern-recognition ↑ Prerequisites: base-conversionmodular-arithmetic
📏 Medium solution 💡 3 insights
Problem
A number is written in base nine with eleven digits, so in ordinary base ten it is huge. Find the remainder when it is divided by 5, without ever needing its full base-ten value.

Pick an answer.

(A)
0
(B)
1
(C)
2
(D)
3
(E)
4
How to solve
Strategy Solve an Easier Related Problem

Converting the whole base-nine numeral into base ten would mean multiplying out 9¹0, a ten-digit number, and adding four more large products. That work is unnecessary because only the remainder is wanted. Remainders survive multiplication and addition: if two numbers leave the same remainder on division by 5, then so do their sums and their products. So each 9 in the expansion can be swapped for the small number it leaves behind, turning a giant computation into an easier related one with single-digit pieces. Once that swap is made, the powers of 9 fall into a short repeating pattern, and the whole problem collapses to adding eleven digits with signs.

1STEP 1

Unpack the base-nine numeral

Unpack it into a sum of powers.

N = 2 · 9¹⁰ + 7 · 9⁹ + 6 · 9⁶ + 5 · 9¹ + 2 · 9⁰
2STEP 2

Replace each nine by what it leaves behind

Nine is minus one modulo five.

9 = 5 + 4 ≡ 4 (mod 5), 9 = 10 - 1 ≡ -1 (mod 5)
3STEP 3

Powers of nine alternate

The powers alternate.

9^k ≡ (-1)^k (mod 5), 9^k ≡ 1 if k is even, 9^k ≡ -1 if k is odd
4STEP 4

Add the digits with alternating signs

Add the digits with alternating signs.

N ≡ 2(1) + 7(-1) + 6(1) + 5(-1) + 2(1) = 2 - 7 + 6 - 5 + 2 = -2 (mod 5)
5STEP 5

Turn negative two into a real remainder

Turning the negative into a real remainder gives 3.

-2 ≡ -2 + 5 = 3 (mod 5), 0 ≤ 3 ＜ 5
Answer
3
Redo the reduction with 4 instead of negative 1 and the answer should not change. Since 9 leaves remainder 4, and 4 squared is 16 which leaves remainder 1, the powers of 9 leave remainders 1, 4, 1, 4, and so on for exponents 0, 1, 2, 3. The even places therefore give 2 times 1 for the 9¹0 digit, 6 times 1 for the 9⁶ digit, and 2 times 1 for the ones digit, while the odd places give 7 times 4 and 5 times 4. The total is 2 + 28 + 6 + 20 + 2 = 58, and 58 = 11 times 5 plus 3, so the remainder is again 3. The two routes agree, and 3 is in the legal range 0 through 4, so the value is consistent.
💡Key takeaway

To find a remainder, never build the giant number: swap the base for the small amount it leaves behind, and the powers collapse into a short repeating pattern.

  • Unpack the base-nine numeral
  • Replace each nine by what it leaves behind
  • Powers of nine alternate
  • Add the digits with alternating signs
  • Turn negative two into a real remainder

More like this

Same archetype — closest grade level first.