A hundred digit number is formed by writing the first few natural numbers in front of each other as follows:

Find the remainders when this number is divided by each of the numbers from 1 to 20.

The number is 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.

Divided by 1 of course leaves remainder of zero, as would any number divided by 1.

The number is odd, so its remainder mod 2 is 1.

54 is a multiple of 3, and therefore the sum of the digits of all the numbers up through 54 is also a multiple of 3. The extra 5 makes the remainder mod 3 equal to 2.

Remainder mod 4 depends on the last two digits: so it's 1.

The number ends in 5 so the remainder mod 5 is zero.

The number is odd and leaves a remainder of 2 mod 3, so the remainder mod 6 is 5.

mod 7 ???

The last three digits, 545, are congruent to 1 mod 8, and thus is the whole number.

54 is a multiple of 9, and therefore the sum of the digits of all the numbers up through 54 is also a multiple of 9. The extra 5 makes the remainder mod 9 equal to 5.

The last digit is 5, so that's the remainder mod 10.

mod 11 ???

The number is 1 mod 4 and 2 mod 3, so is 5 mod 12.

mod 13 ???

mod 14 ???

The number is congruent to 0 mod 5 and 2 mod 3, so is congruent to 5 mod 15.

The last four digits, 3545, have remainder 9 when dividing by 16, and so that's the remainder for the number as a whole.

mod 17 ???

The number is odd and congruent to 5 mod 9 and so is congruent to 5 mod 18.

mod 19 ???

The last two digits, 45, are congruent to 5 mod 20 and thus so is the whole number.

Posted by Charlie on 2006-03-20 11:28:32