2017 AMC 10B Problem 23

Problem 23 of 25HarderNumber Theory

Let

N=123456789101112\dots4344

be the

79

-digit number that is formed by writing the integers from

1

44

in order, one after the other. What is the remainder when

N

is divided by

45?

Show solution

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

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

9.

Thus, the correct answer is C .