Section 006) Chinese Remainder Theorem

If m and n are positive integers which are relatively prime i.e. GCD(m , n ) = 1. Then there exists an integer N such that

$N \equiv a (\mod m)$
$N \equiv b (\mod n)$

Moreover $N \equiv x (\mod mn)$ where x is unique.

This can be proved  but I am not specifying the prrof here

This can be generalized to n  integers.

$N \equiv a_i (\mod m_i)$ where i varying from 1 to n and $m_i$ are pairwise relatively co-prime then there exists x such that

$x = \sum_{i=1}^n\frac{a_ib_iM}{m_i}$ where M is product of all $m_i$ and $b_i$ is determined from M as below

$b_i\frac{M}{m_1}  \equiv 1 \mod m_1$

We illustrate the same with an example below

Problem 1

What would be the least positive . which give the remainder 1 when divided by 7,2 when divided by 9 and 11 when divided by 11 

Solution 1

Let the number be x 

We have remainder 1 when divided by 7,2 when and 3 when divided by 11

So

$x=1\pmod 7\cdots(1)$
$x=2\pmod 9\cdots(2)$
$x=3\pmod {11}\cdots(3)$

Now 7 ,9 and 11 are pair wise co-prime 

So M= 7 * 9 * 11 = 693

So $x = 1 a_1b_1 + 2 a_2b_2 + 3 a_3b_3 \pmod {693}$ as M = 693 

Now let us compute $a_1,a_2,a_3$


$a_1 = \frac{M}{7}  = \frac{693}{7} = 99$
$a_2 = \frac{M}{9}  = \frac{693}{9} = 77$
$a_3 = \frac{M}{11}  = \frac{693}{11} = 63$

Now we need to compute $b_1,b_2,b_3$ such that

$99b_1 =1   \pmod 7$ or $b_1 =1  \pmod 7$ or $b_1 = 2$

$77b_2 =1   \pmod 9$ or $5b_2=1   \pmod 9$ or $b_2 = 2$
  
$63b_3 = 1 \pmod {11}$  or $8b_3 =1 \pmod {11}$ so $b_3 = 7$ as $ 7 * 8 = 56 = 1 \pmod {11}$

I have mentioned the above in hit and trial method because the co-coefficients are low and they can be computed using extended euclidean algorithm as below.

Let us try  the $3^{rd}$ part i.e.$8b_3 =1 \pmod {11}$

That is solve  $8x =1 \pmod {11}$

Or $8x= 1 + 11y$ 

We need to  compute $ 1= 8a + 11b$ where b is negative then a is the inverse of 8

To compute a ,b we have

$11 = 1 * 8 + 3$

So $3 = 11 -8$

$8 = 3 * 2 + 2$ or $2 = 8- 3 * 2 = 8- 2 * (11-8) = 3 * 8 - 2 * 11$

$1 = 3 -2 = (11-8) - ( 3 * 8 - 2 * 11) = 3 * 11 - 4 * 8$

We have found $1 = 8a + 11 b$  where $b = 3$ which is positive

We need to convert it to positive

Knowing $8a + 11 b = 8(a+11t) + 11(b-8t)$ identity if we add 8 to b and subtract 11 from a we get

$1 = 8(-4 +11) + 11(3 -8) = 7 * 8 - 5 * 11$

So $8 * 7  =1 \pmod {11}$

Hence 7 is inverse of 8  

So $x = 1 * 99 * 1 + 2 * 77 * 2 + 3 * 63 * 7 \pmod {693} = 1730 \pmod {693}$

$= 344 \pmod {693}$

So x if of the form $693n + 344$  or lowest x = 344


Problem 2

Find all integers that leave a remainder 1 when divided by either 2 or 5 but divisible by 3.

Solution 2

Let the number be x 

We have remainder 1 when divided by 2 or 5 but divisible by 3

So

$x=1\pmod 2\cdots(1)$
$x=1\pmod 5\cdots(2)$

$x=0\pmod 3 \cdots(3)$

we can combine (1) and (2) are remainders are same to have
$x=1\pmod 10 \cdots(4)$

now we need to solve the following

$x=0\pmod 3 \cdots(5)$

$x=1\pmod {10} \cdots(6)$

we shall use CRT as 3 and 10 are coprimes

M = 3 * 10 = 30

$a_1 = \frac{30}{3}  = 10$
$a_2 = \frac{30}{10}  =3$

Now we need to compute $b_1,b_2,b_3$ such that

$10b_1 =1   \pmod 3 $ or $b_1 =1  \pmod 3$ or $b_1 = 1$ (actually we need not compute as coefficient = 0)

$3b_2 =1   \pmod {10} $ or $b_2=7   \pmod {10}$ or $b_2 = 7$

so the number  = $0 * 10 * 1 + 1 *3 * 7 = 21  \pmod{30}$