NMTC 2K17 Problem 12

Number Theory Level 3

123456 … 424344 123456 \ldots 424344

The large number above has been formed by concatenating the integers 1 to 44.

What is the remainder when this number is divided by 45?

1 9 18 27 44

View wiki
Achal Jain by Achal Jain , 19, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Adding the numbers from 1 to 44 we get that this number has a sum of digits of 990, thus the number has a remainder of 0 mod 9.

To get the numbers remainder mod 5 we simply look at the last digit, namely 4.

So call this large number x. We now know that

x m o d 9 = 0 x mod 9 = 0

x m o d 5 = 4 x mod 5 = 4

We can now use the Chinese Remainder Theorem to calculate that

x m o d 45 = 9 x mod 45 = 9

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...