Question

Let a_n be the integer obtained by writing all the integers from 1 to n from left to right. For example, a_3 = 123 and a_{11} = 1234567891011. Compute the remainder when a_44 is divided by 45.

Answer 1

Answer:

  9

Step-by-step explanation:

The 79-digit number of interest can be formulated as a sum of shorter numbers whose remainders can be computed.

Expanded form

The expanded form of the number can be written as ...

  a_44 = 01×10^78 +23×10^76 +45×10^74 +67×10^72 +89×10^70 +...

  +10×10^68 +11×10^66 +... +43×10^2 +44×10^0

Powers of 10

Each number except the last is multiplied by a power of 10. Powers of 10 modulo 45 are ...

  10 mod 45 = 10

  100 mod 45 = 10

This lets us conclude that any positive power of 10 mod 45 is 10.

Parts of the sum

In short, all of the multiplication by powers of 10 can be collapsed to a single multiplication by 10. Hence, the mod 45 value of a_44 will be ...

  a_44 mod 45 = (((01 +23 +45 +67 +89) +10 +11 +12 +... +43)×10 +44) mod 45

  = (((01 +23 +45 +67 +89) mod 45 + sum(10 .. 43) mod 45)×10 +44) mod 45

  = (((225 mod 45) +(901 mod 45))×10 +44) mod 45

  = ((0 +1)×10 +44) mod 45

Final value

  a_44 mod 45 = 54 mod 45 = 9

__

Additional comment

The result can be confirmed by a suitable calculator.

__

The sum of the 34 numbers from 10 to 43 is the product of their average value (10+43)/2 = 26.5 and their number, 34. (26.5×34) = 901.