Today we are going to learn how to solve for a set of equivalence relations of the form:
$a \equiv r_1\ (mod\ n_1)$
$a \equiv r_2\ (mod\ n_2)$
$.$
$.$
$.$
$a \equiv r_t\ (mod\ n_t)$.
The Chinese Remainder Theorem states that there is solution for $a$ if and only if $n_1,\ n_2,\ ...,\ n_t$ are all mutually coprimes, that is, no two of these divisors has $GCD \gt 1$
$\underline{Understanding\ The\ Algorithm}$
We will learn this method using an example.
Find the minimum positive integer $a$ such that $a$ leaves remainders of $9,\ 7,\ 5$ when divided by $11,\ 12,\ 13$ respectively.
Let us write the equivalence relation for the given values, as below:
$a \equiv 9\ (mod\ 11)$
$a \equiv 7\ (mod\ 12)$
$a \equiv 5\ (mod\ 13)$
Let us call the product $11 \times 12 \times 13 = 1716$ as $N$.
-----------book page break-----------
To find out a solution for $a$, we will create a table containing the following columns:
$r_i$ containing the values of the remainders for each $i$.
$N_i$ containing the values of $\dfrac{N}{n_i}$ for each corresponding $i$
$b_i$ containing the values of the multiplicative inverse of $N_i$ modulo $n_i$, that is $b_i \equiv (N_i)^{-1}\ (mod\ n_i)$
$a_i$ containing the product $r_i \times N_i \times b_i$
Let us draw the table and fill in the values of the first two columns
$r_i$
$N_i$
$b_i$
$a_i$
$9$
$\dfrac{11 \times 12 \times 13}{11} = 156$
$7$
$\dfrac{11 \times 12 \times 13}{12} = 143$
$5$
$\dfrac{11 \times 12 \times 13}{13} = 132$
Now let us fill up the third column by finding the inverses.
$b_1 \equiv 156^{-1}\ mod(11)$
We know that $156 \equiv 2\ (mod\ 11)$
Therefore,
$156^{-1}\ mod(11) = 2^{-1}\ mod(11)$
Since both $2$ and $11$ are very small numbers, we can find the inverse by simple inspection.
Note that if the number, $11$ is replace by a larger number you might find the method described more efficient to find the inverse.
-----------book page break-----------
Similarly $b_2 \equiv 143^{-1}\ (mod\ 12)$
$143 \equiv 11\ (mod\ 12)$
Therefore,
$143^{-1}\ mod(12) = 11^{-1}\ mod(12) = 11$ again by inspection.
$b_3 \equiv 132^{-1}\ (mod\ 13)$
$132 \equiv 2\ (mod\ 13)$
$132^{-1}\ (mod\ 13) = 2^{-1}\ (mod\ 13) = 7$
Now we can fill up the remaining two columns of our table as follows:
$r_i$
$N_i$
$b_i$
$a_i$
$9$
$156$
$6$
$9 \times 156 \times 6 = 8424$
$7$
$143$
$11$
$7 \times 143 \times 11 = 11011$
$5$
$132$
$7$
$5 \times 132 \times 7 = 4620$
Summation of all the $a_i$ values will give us $a$ result which will satisfy the given three equivalence relation, and to find the least value of $a$ that satisfies them we have to take the remainder modulo $N$ of our result.
So, to avoid large calculations we will take the remainders first then add them.
Our result is still greater then $N$, therefore we will take one more remainder modulo $N$.
$a_{min} = 3463\ modulo\ 1716 = 31$
Let us verify our result before we move on to the next step:
$31 = 2 \times 11 + 9$
$31 = 2 \times 12 + 7$
$31 = 2 \times 13 + 5$
-----------book page break-----------
Therefore, $31$ will leave remainders of $9$, $7$ and $5$ when divided by $11$, $12$ and $13$ respectively, as required by the problem, and $31$ is the smallest positive integer to satisfy these conditions.
$\underline{Proof\ Of\ Correctness}$
Now let us understand why this works and gives the correct result, when we solve the equivalence relation using the method shown till now.
First of all let us understand why all $n_i$ values need to be mutually coprime.
Let us say they are not, that is for some $i = j$ and $i = k$, $n_j$ and $n_k$ share a common factor greater than $1$, then
$N_j = \dfrac{N}{n_j}$ will still contain $n_k$ as a factor, therefore, will share the same common factor with $n_j$, and $N_j$ will not be a coprime to $n_j$.
Therefore, $N_j^{-1}\ (mod\ n_j)$ will not exist, and this value will be impossible to find.
$\Rightarrow N_j \equiv 0\ (mod\ n_k)$ for each $k \ne j$
Therefore, when we calculate $a\ modulo \ n_j$ all terms are equivalent to $0\ (mod\ n_j)$, and the only non-zero value is contributed by the term $r_jN_jb_j$
Since we have computed $b_j$ as inverse of $N_j\ (mod\ n_j)$,