2017 AMC 10B Problem 23

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

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

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

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