2021 AMC Fall 10A Problem 12

P11-15~3 minPrint

Modular Arithmetic Bases & Digits Set up the equation/formula and compute; no special trick needed

The base-nine representation of the number $N$ is $27{,}006{,}000{,}052_{\text{nine}}.$ What is the remainder when $N$ is divided by $5?$

Show solution without answering

Key insight

Powers of 9 leave remainders 1, 4, 1, 4, ... when divided by 5. Multiply each nonzero digit by the remainder for its place and add.

Solution

Converting this 11-digit base-nine number to base ten would take a long time. We only need the remainder when dividing by $5$ , so we can work with remainders the whole way.

What the digits mean. In base nine, each place is worth $9$ times the place to its right: $1, 9, 81, 729, \ldots$ Reading $27{,}006{,}000{,}052_{\text{nine}}$ from the right:

place (from the right)	0	1	2	3	4	5	6	7	8	9	10
digit	2	5	0	0	0	0	6	0	0	7	2

2. Remainders of the place values. Divide the place values by $5$ :
- $1$ leaves remainder $1$ .
- $9$ leaves remainder $4$ .
- $81$ leaves remainder $1$ .
- $729$ leaves remainder $4$ .

The pattern keeps going: multiplying by $9$ turns remainder $1$ into $4$ , and turns $4$ into $36$ , which has remainder $1$ . So even places have remainder $1$ and odd places have remainder $4$ .
3. Only the nonzero digits matter. Multiply each by the remainder for its place:
- place 0: $2 \times 1 = 2$
- place 1: $5 \times 4 = 20$
- place 6: $6 \times 1 = 6$
- place 9: $7 \times 4 = 28$
- place 10: $2 \times 1 = 2$
4. Add and divide. $2 + 20 + 6 + 28 + 2 = 58$ , and $58 = 11 \times 5 + 3$ , so the remainder is $3$ .

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

Why this works

When you only care about a remainder, you can replace every number by its remainder at any step: in sums and in products. Here $9$ is one less than $10$ , a multiple of $5$ , so its remainder $4$ acts like " $-1$ ". In the language of congruences, $9 \equiv -1 \pmod 5$ , which means $9$ and $-1$ leave the same remainder when divided by $5$ . So the places alternate plus and minus, just like the divisibility test for $11$ in base ten.

Alternative approach

Use the " $-1$ " idea directly: add the digits with alternating signs, starting with $+$ at the units place. The nonzero digits give $2 - 5 + 6 - 7 + 2 = -2$ . A number that is $2$ less than a multiple of $5$ leaves remainder $5 - 2 = 3$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Write $N$ in expanded form: with digits $d_{10} d_9 \dots d_1 d_0 = 2,7,0,0,6,0,0,0,0,5,2$ ,
$N = \sum_{i=0}^{10} d_i \cdot 9^i.$

Since $9 \equiv -1 \pmod 5$ , we have $9^i \equiv (-1)^i \pmod 5$ . So modulo $5$ , $N$ is the alternating sum of its base-nine digits, with the units digit positive:
$N \equiv d_0 - d_1 + d_2 - \cdots + d_{10} \pmod 5.$

Only five digits are nonzero: $d_0 = 2$ , $d_1 = 5$ , $d_6 = 6$ , $d_9 = 7$ , $d_{10} = 2$ . Even positions get $+$ , odd positions get $-$ :
$N \equiv 2 - 5 + 6 - 7 + 2 = -2 \equiv 3 \pmod 5.$

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

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Number Theory, Chapter 10: Units Digits
Introduction to Number Theory, Chapter 9: Base Number Arithmetic