2017 AMC 10B Problem 23

P21-25~5 minPrint

Modular Arithmetic Bases & Digits Use the answer choices (mod checks, size, form) to eliminate or select Set up the equation/formula and compute; no special trick needed

Let $N=123456789101112\dots4344$ be the $79$ -digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$ ?

Show solution without answering

Key insight

Split 45 into 5 and 9. N ends in 4, so its remainder by 5 is 4; its digit sum matches 1 through 44 added up, 990.

Solution

Dividing a 79-digit number by $45$ directly is hopeless. But $45 = 5 \cdot 9$ , and there are easy tests for $5$ and for $9$ . So find the remainder by $5$ and the remainder by $9$ separately.

1. Remainder by 5. Only the last digit matters for $5$ . $N$ ends in $4$ , so it leaves remainder $4$ when divided by $5$ .
2. Remainder by 9. A number leaves the same remainder by $9$ as the sum of its digits. For example, $44$ has digit sum $8$ , and $44 = 36 + 8$ leaves remainder $8$ too.
3. The digits of $N$ are the digits of $1, 2, 3, \ldots, 44$ written one after another. By step 2, each of these numbers has digits adding to something with the same remainder by $9$ as the number itself. So the digit sum of $N$ has the same remainder by $9$ as
$1 + 2 + \cdots + 44 = \frac{44 \cdot 45}{2} = 990.$
4. $990 = 9 \cdot 110$ , so $N$ is a multiple of $9$ .
5. Put them together. We want a remainder $r$ between $0$ and $44$ that is a multiple of $9$ and leaves $4$ when divided by $5$ . The multiples of $9$ in that range are $0, 9, 18, 27, 36$ ; divided by $5$ they leave $0, 4, 3, 2, 1$ . Only $r = 9$ works.
6. Why this is right: $N - 9$ is a multiple of $9$ (both $N$ and $9$ are) and a multiple of $5$ (both leave $4$ ). A number that is a multiple of both $5$ and $9$ is a multiple of $45$ . So $N$ leaves remainder $9$ when divided by $45$ .

The answer is $\boxed{\textbf{(C)}\ 9}$ .

Why this works

When the divisor is a product of two numbers with no common factor, such as $45 = 5 \cdot 9$ , handle each piece with its own easy test and then combine. The digit-sum test for $9$ also works on pieces: gluing numbers together adds their digit sums, so the whole $79$ -digit number behaves like the plain sum $1 + 2 + \cdots + 44$ .

Alternative approach

Use the answer choices. The remainder must be a multiple of $9$ , which leaves only $9$ and $18$ . It must also leave $4$ when divided by $5$ : $9$ does, $18$ does not.

If you prefer to add the digits directly: $1$ to $9$ give $45$ ; the tens digits of $10$ to $44$ give $10 \cdot 1 + 10 \cdot 2 + 10 \cdot 3 + 5 \cdot 4 = 80$ ; their ones digits give $3 \cdot 45 + (0 + 1 + 2 + 3 + 4) = 145$ . The total $45 + 80 + 145 = 270 = 9 \cdot 30$ is a multiple of $9$ .

Concise solution

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

Since $45 = 5 \cdot 9$ with $\gcd(5, 9) = 1$ , find $N$ modulo $5$ and modulo $9$ separately.

Mod $5$ : only the last digit matters, and $N$ ends in $4$ . So $N \equiv 4 \pmod 5$ .

Mod $9$ : a number is congruent to its digit sum mod $9$ . The digits of $N$ are the digits of $1, 2, \dots, 44$ , and each integer $k$ is congruent to its own digit sum mod $9$ . Hence
$N \equiv 1 + 2 + \dots + 44 = \frac{44 \cdot 45}{2} = 990 \equiv 0 \pmod 9,$
because $9 + 9 + 0 = 18$ is a multiple of $9$ .

Now find the residue mod $45$ that is $0 \bmod 9$ and $4 \bmod 5$ . The multiples of $9$ below $45$ are $0, 9, 18, 27, 36$ ; their residues mod $5$ are $0, 4, 3, 2, 1$ . Only $9$ works.

The answer is $\boxed{\textbf{(C)}\ 9}$ .

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