What is the smallest number which leaves a remainder:
9 when divided by 10;
8 when divided by 9;
7 when divided by 8;
6 when divided by 7;
5 when divided by 6;
4 when divided by 5;
3 when divided by 4;
2 when divided by 3;
1 when divided by 2 ?

[ In other words: Find the Least number which when divided by 'N' leaves a remainder '(N-1)', for N = 1,2,3,4,........,9,10].

The answer will just be one less than the lowest common multiple of the numbers 2-10. To find that number, simply eliminate any common prime factors:
2 3 4 5 6 7 8 9 10
2, 3, 5, and 7 are prime and obviously must be factors of the solution:
2 3 4 5 6 7 8 9 10
Also, we see that these numbers take care of 6 (2*3) and 10 (2*5):
2 3 4 5 6 7 8 9 10
That leaves only 4, 8, and 9. The factor of 2 leaves 4 and 8 with 2 and 4, respectively, to take care of, or just another factor of 4 will be needed to cover both.
2 3 4 5 6 7 8 9 10 (4)
Finally, another factor of 3 is needed to make up for the 9:
2 3 4 5 6 7 8 9 10 (4 3)

All in all, the lowest common factor of the numbers two through ten is the product of 2, 3, 3, 4, 5, and 7. This is 2520. One less than this is 2519, and should leave a remainder when divided by each number:
2519/10 = 251+9/10
2519/9  = 279+8/9
2519/8  = 314+7/8
2519/7  = 359+6/7
2519/6  = 419+5/6
2519/5  = 503+4/5
2519/4  = 629+3/4
2519/3  = 839+2/3
2519/2  =1259+1/2

Posted by DJ on 2003-05-29 07:48:24