Is there a possible explanation in plain English how to use the Chinese Reminder Theorem?

Question

For example, if it is the problem of

Find the smallest integer that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11

In some explanation such as in this article it started to use mod, and the whole explanation seemed to very difficult to understand. Is there a more plain English explanation of how this is solved?

Answer 1

Find the smallest integer, $n$, that leaves

$\text{A remainder of $3$ when divided by $5$.}\tag{1}$

$\text{A remainder of $5$ when divided by $7$.}\tag{2}$

$\text{A remainder of $7$ when divided by $11$.}\tag{3}$

Without using moduli, the Chinese Remainder theorem says that the integers $n$ that meet the above three requirements must be of the form $385A + r$ for a unique $0 \le r < 385$; where $385 = 5 \cdot 7 \cdot 11$.

Looking at the first two conditions, there must exists integers $u$ and $v$ such that $$\text{$n=5u+3\quad$ and $\quad n = 7v + 5$}$$

So

$$\text{$7n=35u+21\quad$ and $\quad 5n = 35v + 25$}$$

We find (Bezout's Identity) that $-2 \cdot 7n + 3 \cdot 5n = n$. So

\begin{align} n &= -2 \cdot 7n + 3 \cdot 5n \\ n &= -2(35u+21) + 3(35v + 25) \\ n &= 35(-2u+3v) + 33 \\ n &= 35w + 33 \\ \end{align}

What have we gained from this? The CRT guarantees that every integer $n$ that satisfies conditions $(1)$ and $(2)$ must be of the form $35w + 33$ for some integer $w$.

Condition $(3)$ tells us that there must exists some integer, $x$, such that $n = 11x + 7$. So

$$\text{$11n=385w+363\quad$ and $\quad 35n = 385x + 245$}$$

We find that $16\cdot 11n - 5 \cdot 35n = n$ So

\begin{align} n &= 16\cdot 11n - 5 \cdot 35n \\ n &= 16(385w+363) - 5(385x + 245) \\ n &= 385(16w-5x) + 4583\\ n &= 385(16w-5x) + 11\cdot 385 + 348\\ n &= 385(16w-5x+11) + 348\\ n &= 385y + 348\\ \end{align}

A quick check shows that 348 satisfies conditions $(1), (2)$, and $(3)$.

Answer 2

First you solve $5a + 7 b = 1$ and then $35c + 11 d = 1.$

$$ \gcd( 7, 5 ) = ??? $$

$$ \frac{ 7 }{ 5 } = 1 + \frac{ 2 }{ 5 } $$ $$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 1 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 7 }{ 5 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 1 \\ \frac{ 1 }{ 1 } & \mbox{digit} & 2 \\ \frac{ 3 }{ 2 } & \mbox{digit} & 2 \\ \frac{ 7 }{ 5 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 7 \cdot 2 - 5 \cdot 3 = -1 $$

======================================

$$ \gcd( 35, 11 ) = ??? $$

$$ \frac{ 35 }{ 11 } = 3 + \frac{ 2 }{ 11 } $$ $$ \frac{ 11 }{ 2 } = 5 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 3 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 3 }{ 1 } & & \frac{ 16 }{ 5 } & & \frac{ 35 }{ 11 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 3 \\ \frac{ 3 }{ 1 } & \mbox{digit} & 5 \\ \frac{ 16 }{ 5 } & \mbox{digit} & 2 \\ \frac{ 35 }{ 11 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 35 \cdot 5 - 11 \cdot 16 = -1 $$

===========================================

More to come. Checking typesetting..

$$ 7 \cdot (-2) + 5 \cdot 3 = 1. $$ Now multiply $7(-2),5(3)$ by the $3,5$ $$ 3 \cdot 7 \cdot (-2) + 5 \cdot 5 \cdot 3 = -42 + 75 = 33. $$ and

We now want remainder $33$ when divided by $35$ and $7$ when divided by $11$ and $$ 35 \cdot (-5) + 11 \cdot 16 = 1, $$ Now multiply $35(-5),11(16)$ by the $7,33$ $$ 7 \cdot 35 \cdot (-5) + 33 \cdot 11 \cdot 16 = -1225 + 5808= 4583. $$

You can check that the remainder when $4583$ is divided by $5$ really is $3,$ when divided by $7$ really is $5,$ when divided by $11$ really is $7.$

Now, $$ 5 \cdot 7 \cdot 11 = 385. $$ If we subtract $385$ we get the same remainders. So, solutions are $$ 4583, \; 4198, \; 3813, \;3428, \; 3043, , \ldots, \; 733, \; 348, \; -37 $$

Answer 3

Find the smallest integer that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11

We want to find a solution to:

$$ \begin{align} x&\equiv 3 \pmod 5\\ x&\equiv 5 \pmod 7\\ x&\equiv 7 \pmod {11} \end{align} $$

The solution is unique $\pmod {385}$.

We can find a simple formula for this, by first finding the solutions to:

$$ \begin{align} x&\equiv 1 \pmod 5\\ x&\equiv 0 \pmod 7\\ x&\equiv 0 \pmod {11} \end{align} $$ $$ \begin{align} x&\equiv 0 \pmod 5\\ x&\equiv 1 \pmod 7\\ x&\equiv 0 \pmod {11} \end{align} $$ $$ \begin{align} x&\equiv 0 \pmod 5\\ x&\equiv 0 \pmod 7\\ x&\equiv 1 \pmod {11} \end{align} $$

By using the Extended Euclidean Algorithm, we find:

$$ \begin{align} x\equiv 231\pmod {385}\\ x\equiv 330\pmod {385}\\ x\equiv 210\pmod {385}\\ \end{align} $$

Hence the solution to:

$$ \begin{align} x&\equiv a \pmod 5\\ x&\equiv b \pmod 7\\ x&\equiv c \pmod {11} \end{align} $$

is:

$$231a+330b+210c\pmod{385}$$

For $a=3,b=5,c=7$, we get $693+1650+1470=3813\equiv 348\pmod{385}$.

Answer 4

It's definitely worthwhile learning a little bit about modular arithmetic for questions such as this.

But if you want to know in very concrete terms how to solve questions such as this, here's an attempt.

Suppose you want a number $n$ (not necessarily the least, we'll handle that later) with remainder $3$ when divided by $5$ and $5$ when divided by $7$, which we write as $n \equiv 3 \mod 5$ and $n \equiv 5 \mod 7$. The Chinese remainder theorem tells us that this is possible, because $5$ and $7$ are relatively prime, i.e. have no common factor greater than $1$.

We start out by finding integers $x$ and $y$ such that $5 x + 7 y = 1$. If so, then $5 x = 1 - 7 y$ is an integer $u$ such that $u \equiv 0 \mod 5$ and $u \equiv 1 \mod 7$, while $7 y = 1 - 5 x$ is a number $v$ such that $v \equiv 1 \mod 5$ and $v \equiv 0 \mod 7$. Combining these, $n = 5 u + 3 v$ would have $n \equiv 5 \cdot 0 + 3\cdot 1 = 3 \mod 5$ and $n \equiv 5 \cdot 1 + 3 \cdot 0 = 5 \mod 7$.

The method for finding $x$ and $y$ is called the Euclidean algorithm. It goes like this. We want $5 x + 7 y = 1$. Write $7 = 5 + 2$, so $5 x + 5 y + 2 y = 5 (x + y) + 2 y$. Thus with $x_1 = x + y$, we want to solve $5 x_1 + 2 y = 1$ (a similar equation to what we started with, but with smaller coefficients). If we can do that, then we can take $x = x_1 - y$. to solve our original equation.

Similarly, $5 = 2 \cdot 2 + 1$, so $5 x_1 + 2 y = x_1 + 2 (2 x_1 + y) = x_1 + 2 y_1$ where $y_1 = 2 x_1 + y$. But the equation $x_1 + 2 y_1 = 1$ is easy: we can see at a glance that $x_1 = 1$, $y_1 = 0$ is a solution. Then working backwards, $y = y_1 - 2 x_1 = -2$ and $x = x_1 - y = 1 - (-2) = 3$. So we have found $x = 3$ and $y = -2$ such that $5 x + 7 y = 1$. We then take $u = 5 x = 15$ and $v = 7y = -14$, and $n = 5 u + 3 v = 33$, which has $n \equiv 3 \mod 5$ and $n \equiv 5 \mod 7$.

Now, $n = 33$ is not the only possible solution. In fact, we could get another solution by adding or subtracting any multiple of $5 \times 7 = 35$. Since $5$ and $7$ are relatively prime, the theory tells us that those are all the other solutions: if $m$ is another solution, $n - m$ would have to be a multiple of $5$ and a multiple of $7$, and therefore a multiple of $35$. Now in this particular case $33 - 35$ is negative, in fact $33$ is the smallest positive solution.

Now, what about the original problem with $n \equiv 7 \mod 11$ in addition to $n \equiv 3 \mod 5$ and $n \equiv 5 \mod 7$? We know now that from the first two conditions we need $n$ to differ from $33$ by a multiple of $35$, i.e. $n \equiv 33 \mod 35$. So we go through a similar procedure, finding $x$ and $y$ such that $35 x + 11 y = 1$, etc. I'll leave the details to you.