2017 AMC 12B Problem 19

Problem 19 of 25HarderNumber Theory

Let

N = 123456789101112\ldots4344

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

The last digit of

N

4,

N \equiv 4 \pmod 5.

For mod

9,

sum the digits: the numbers

1

–

9

contribute their digits, the tens digits of

10

–

44

and the units digits together sum to

270,

which is a multiple of

9,

N \equiv 0 \pmod 9.

The number

N - 9

is then a multiple of

9,

and its last digit is

5,

so it is a multiple of

5;

hence

N - 9

is a multiple of

45.

Therefore

N \equiv 9 \pmod{45}.

Thus, the correct answer is C.

Tagged: modular arithmetic · divisibility · digits