Expert: Vijilant - 2/8/2010

Question
[Question 1] Find, with proof, the smallest positive integer n that satisfy all the congruences.
n = 1 (mod 2)
n = 2 (mod 3)
n = 3 (mod 4)
n = 4 (mod 5)
n = 5 (mod 6)
n = 6 (mod 7)
n = 7 (mod 8)
n = 8 (mod 9)
n = 9 (mod 10)

I tried to put some reistrictions on n (ie. n<3 & odd since n = 1 (mod 2)) but this approach seems to take too much time & I don't think I'm technically proving it.



[Question 2]  (172195)*(572167) = 985242x6565
figure out x with out redoing the multiplication.

I know x=9 cause I typed it in the calculator but I don't know how to do it without actually doing the multiplication.

Answer
Hello Kai
This looks hard, but is easy, because in each case, n = -1 (mod a) for each a.
So we need to work out the lcm of the numbers 2 to 10.  This will be 2^3*3^2*5*7 = 2520.
So n = -1 (mod 2520), so n = 2521 is the smallest.

For this problem all we need is to do it (mod 9)  To calculate a base ten number (mod 9) you just have to add the digits, since each power of ten = 1 (mod 9).  If you get more than 9, keep adding the digits.
So your calc is 7*1 = 7 + x (mod 9), and that gives x = 0 (mod 9).
This proves that you didn't know the answer.  The answer is x = 0 or 9.
But at least, you tried!

Best wishes

vijilant