1322.14 – Chinese Remainders

Here's the story. $N$ is a positive integer. When $N$ is divided by 3, the quotient is $Q$ with remainder 1. When $Q$ is divided by 4, the quotient is $R$ with remainder 1. When $R$ is divided by 5, the quotient is $S$ with remainder 1. All three of the numbers, $Q, R, S,$ are positive integers.

Find the smallest possible value for $N$ that makes all this work.

Solution

All four of the numbers, $N$ , $Q$ , $R$ , and $S$ have a minimal property. $N$ is smallest such that when divided by 3 the quotient is $Q$ and remainder 1. $Q$ has a similar property: the divisor is 4 but the remainder is also 1. Ditto for $R$ except the divisor is 5 and the quotient is $S$ . When we come to $S$ there is no division requirement. Good deal! $S$ will be the easiest of all the numbers to discover. All that $S$ has to be is a positive integer. So we can let $S = 1$ , the smallest positive number period.

Now, all that $R$ has to do is have quotient $S$ with remainder 1. Start with $S = 1$ . Increasing by steps of 5, so as not to disturb the "when divided by 5" part, we reach $5 + 1 = 6$ , in one step and so arrive at the smallest number that when divided by 5 gives $S = 1$ and has remainder 1. This is $R = 6$ .

To find $Q$ , we start again with 1, but add 4's this time until we reach a number which, when divided by 4, gives as quotient $R = 6$ and still has remainder 1. This would be $1 + 4 \times 6 = 25$ . Thus $Q = 26$ .

Finally, starting again with 1, we add 3's this time to reach a number that gives $Q = 25$ when divided by 3 with remainder 1. This would be $N = 1 + 3 \times 25 = 76$ . This is the smallest number satisfying all the requirements of the problem.

The answer is $N = 76$ .

Check:

$\dfrac{76}{3} = 25 \dfrac{1}{3}$
$\dfrac{25}{4} = 6 \dfrac{1}{4}$
$\dfrac{6}{5} = 1 \dfrac{1}{5}$

If you're wondering what this has to do with China, this problem is an example of the Chinese Remainder Theorem, which can be explored on Google.