Question

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

$1$

$4$

$9$

$18$

$44$

Answer: C

Concepts:modular arithmetic Chinese Remainder Theorem digits

Difficulty rating: 1660

Solution:

To find the remainder when divided by $45,$ we must find the remainder when divided by $5$ and $9.$ The remainder when divided by $5$ is the remainder when the units digit is divided by $5,$ making it $4.$

To find the remainder when divided by $9,$ we usually find the sum of the digits. However, each double digit number has the same remainder when divided by $9$ as its digit sum, so we can just sum the integers from $1$ to $44,$ because each integer is congruent to its own digit sum. This sum is $\dfrac{44\cdot45}{2}=990,$ which is a multiple of $9.$ Thus, $N$ is a multiple of $9.$

Since it is a multiple of $9$ and has a remainder of $4$ when divided by $5,$ the remainder when divided by $45$ is $9.$

Thus, the correct answer is C .

2017 AMC 10B Problem 23

Answer: C

Difficulty rating: 1660

Solution:

Problem 23 in Other Years