The Chinese Remainder Theorem (the CRT)

[DeaconJohn]

Find the lowest number that has a remainder of
1 when divided by 2,
2 when divided by 3,
3 when divided by 4,
4 when divided by 5, and
5 when divided by 6.

It is possible to solve this by applying the general algorithm that solves Chinese Remainder problems. But, for this special case of the CRT, there is an much quicker way. You just have to look at it right and the answer pops out. ...

Naturally, the point of this problem is more about finding the trick than it is about finding the right answer.

Hints:
6=3x2 and 4 = 2x2.
Problem Source:
Problem 35 on p. 11 in Chp. 1 of Carter and Russell, "The Complete Book of Fun Maths"

 

[daskalou]

Is it 59?

 

[DeaconJohn]

Is it 59?

Yes!

Solution Explained:

If you multiply all the numbers in the right hand column together and subtract one, you get a number that satisfies all the conditions, except there are smaller numbers that work too.

The least common multiple minus one is the smallest number that works. And that is 59.

Relationship with the Chinese Remainder Theorem spelled out:

To solve the problem using the usual proof of the CRT, one applies the Eucledian algorithm. The Eucledian algorithm is often first introduced as a method of computing the gcd, and, given the gcd, one can easily compute the lcd. [I forget how this last demonstration goes. If someone could remind me, that would be great.]

Hence this problem presents the CRT as a generalization of the computation of the gcd using the Eucledian algorithm.

 

[snipez90]

Solution:

Spoiler

Ah, I've seen this trick before. Denote the number we're looking for as x and view the problem in terms of congruencies and it should be evident what happens when you add 1 to x. Then find the lcm of the product of the divisors in the problem. Count 2, 3, another 2 (for 4), 5, and 6 is covered. So x+1 = 2*2*3*5 => x = 59.

 

[DeaconJohn]

Solution:

Spoiler

Ah, I've seen this trick before. Denote the number we're looking for as x and view the problem in terms of congruencies and it should be evident what happens when you add 1 to x. Then find the lcm of the product of the divisors in the problem. Count 2, 3, another 2 (for 4), 5, and 6 is covered. So x+1 = 2*2*3*5 => x = 59.

Snipez90,

All I can say is "Excellent." Really, a nice explanation.

DJ

 

[woverin]

thx very much. Your soln is very useful