2017 AMC 10B Problem 23

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

A modulus that factors into coprime pieces should be attacked one piece at a time: $5$ is controlled by the last digit and $9$ by the digit sum. The digit-sum step hides a second trick: concatenating numbers adds their digit sums, so the total digit sum is congruent to $1 + 2 + \dots + 44$ mod $9$ without touching individual digits.

Use the answer choices: the remainder must be a multiple of $9$ (only $9$ and $18$ qualify) and must be $4 \bmod 5$, which eliminates $18$. Alternatively, check the digit sum directly: the one-digit numbers contribute $45$, the tens digits of $10$ to $44$ contribute $10(1+2+3) + 5 \cdot 4 = 80$, and the units digits contribute $3 \cdot 45 + (0+1+2+3+4) = 145$; total $270 = 9 \cdot 30$.

• Computing the digit sum digit by digit (and slipping) instead of noticing that the digit sum of a block equals that block's value mod 9, so the total is 1 + 2 + ... + 44 mod 9.
• Answering $4$ (choice B) from the mod-$5$ residue alone, or $18$ by mishandling the mod-$5$ check on multiples of $9$.