Chinese remainder theorem. Apply the same and find X for the given set of congruent equations using CRT. a) X = 1(mod 5) X = 2(mod 7) X = 3(mod 9) X = 4(mod 11

Chinese Reminder Theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

For example: - if we have N chocolates if divides among 5 kids then we are left with 3 chocolates and if N chocolates divided among 4 students and we are left with 3 chocolates then with this theorem we can find the value of N

The Equation would be
X ≡ rem 0 ,
X ≡ rem 1 ,
X ≡ rem 2 ,
… .. X ≡ rem n And num [0] , num [1], ……..num [n] ) must be co primes to one another.

For example, No 1 X ≡ 1 ( mod 5)
X ≡ 3 ( mod 7)
gcd (5,7) = 1
As gcd of 5,7 is 1 It is a co-prime the value of x exists

For example, No 2 X ≡ 2 ( mod 3)
X ≡ 3 ( mod 4)
X ≡ 1 ( mod 5)
gcd (3,4) = gcd (4,5) = gcd (3,5) = 1
As gcd of 3,4,5 is 1 It is a co-prime the value of x exists

Chinese Reminder Theorem
standard equation X ≡ ai mod mi
X ≡ a1 mod m1
X ≡ a2 mod m2
X ≡ a3 mod m3
Step 1: - gcd (m1, m2) = gcd (m2, m3) = gcd (m1, m3) = 1 All are co-prime

Step 2: - x = (M1 X1 a1 + M2 X2 a2 + M3 X3 a3 + M4 X4 a4 …………...+ Mn Xn an) mod M where M = m1 * m2 * m3 …………. mn
Mi = M / mi
For example: - M1 = M / m1
Mi Xi = 1 mod mi [Xi – Multiplicative Inverse]
For example: - M1 X1 = 1 mod m1

Numerical
X ≡ 1 mod 5
X ≡ 1 mod 7
X ≡ 3 mod 11

Compare above equation with this standard equation X ≡ ai mod mi
a1 = 1, a2 = 1, a3 = 3 & m1 = 5, m2 = 7, m3= 11
Step 1: - gcd (m1, m2) = gcd (m2, m3) = gcd (m1, m3) = 1
gcd (5,7) = gcd (7,11) = gcd (5,11) = 1
All are co-prime
X exists.
Step 2: - x = (M1 X1 a1 + M2 X2 a2 + M3 X3 a3 + M4 X4 a4 …………...+ Mn Xn an) mod M
where M = m1 * m2 * m3 …………. mn
M = 5 * 7* 11 = 385

Mi = M / mi
M1 = M / m1 = 385 / 5 = 77
M2 = M / m2 = 385 / 7 = 55
M3 = M / m3 = 385 / 11 = 35

Mi Xi = 1 mod mi [Xi – Multiplicative Inverse]
M1 X1 = 1 mod m1
77 X1 = 1 (mod 5) ……… [77 % 5 = 2]
2 X1 = 1 (mod 5) ……… [Check all possible values of X1 so we get reminder as 1]
X1 = 3 ……………. [2 * 3 = 6 mod 5 = 1]

M2 X2 = 1 mod m2
55 X2 = 1 (mod 7) ……… [55 % 7 = 6]
6 X2 = 1 (mod 7) ……… [Check all possible values of X2 so we get reminder as 1]
X2 = 6 ……………. [6 * 6 = 36 mod 7 = 1]

M3 X3 = 1 mod m3
35 X3 = 1 (mod 11) ……… [35 % 11 = 2]
2 X3 = 1 (mod 11) ……… [Check all possible values of X3 so we get reminder as 1]
X3 = 6 ……………. [2 * 6 = 12 mod 11 = 1]

X1 = 3, X2 = 6, X3 = 6, M1= 77, M2= 55, M3= 35
a1 = 1, a2 = 1, a3 = 3, m1 = 5, m2 = 7, m3= 11

x = (M1 X1 a1 + M2 X2 a2 + M3 X3 a3) mod M
= (77 * 3 * 1 + 55 * 6 * 1 + 35 * 6 * 3) mod 385
= (231 + 330 + 630) mod 385
= 1191 mod 385
= 36
x = 36

To Verify the answer: - x mod mi = ai
36 mod 5 = 1
36 mod 7 = 1
36 mod 11 = 3

Numerical 2
X ≡ 1 mod 5
X ≡ 2 mod 7
X ≡ 3 mod 9
X ≡ 4 mod 11

Compare above equation with this standard equation X ≡ ai mod mi
a1 = 1, a2 = 2, a3 = 3, a4 = 4 & m1 = 5, m2 = 7, m3= 9, m4= 11
Step 1: -
gcd (m1, m2) = gcd (m2, m3) = gcd (m3, m4), gcd (m1, m4), = 1
gcd (5,7) = gcd (7,9) = gcd (9,11) = gcd (5,11) = 1
All are co-prime
X exists.
Step 2: - x = (M1 X1 a1 + M2 X2 a2 + M3 X3 a3 + M4 X4 a4 …………...+ Mn Xn an) mod M
where M = m1 * m2 * m3 * m4
M = 5 * 7 * 9 * 11 = 3465

Mi = M / mi
M1 = M / m1 = 3465 / 5 = 693
M2 = M / m2 = 3465 / 7 = 495
M3 = M / m3 = 3465 / 9 = 385
M4 = M / m4 = 3465 / 11 = 315

Mi Xi = 1 mod mi [Xi – Multiplicative Inverse]
M1 X1 = 1 mod m1
693 X1 = 1 (mod 5) ……… [693 % 5 = 3]
3 X1 = 1 (mod 5) ……… [Check all possible values of X1 so we get reminder as 1]
X1 = 2 ……………. [3 * 2 = 6 mod 5 = 1]

M2 X2 = 1 mod m2
495 X2 = 1 (mod 7) ……… [495 % 7 = 5]
5 X2 = 1 (mod 7) ……… [Check all possible values of X2 so we get reminder as 1]
X2 = 3 ……………. [5 * 3 = 15 mod 7 = 1]

M3 X3 = 1 mod m3
385 X3 = 1 (mod 9) ……… [385 % 9 = 7]
7 X3 = 1 (mod 9) ……… [Check all possible values of X3 so we get reminder as 1]
X3 = 4 ……………. [7 *4 = 28 mod 9 = 1]

M4 X4 = 1 mod m3
315 X4 = 1 (mod 11) ……… [315 % 11 = 7]
7 X4 = 1 (mod 11) ……… [Check all possible values of X4 so we get reminder as 1]
X4 = 8 ……………. [7 * 8 = 56 mod 11 = 1]

X1 = 2, X2 = 3, X3 = 4, X4= 8, M1= 693, M2= 495, M3= 385, M4 = 315
a1 = 1, a2 = 2, a3 = 3, a4 = 4 & m1 = 5, m2 = 7, m3= 9, m4= 11

x = (M1 X1 a1 + M2 X2 a2 + M3 X3 a3 + M4 X4 a4) mod M
= (693 * 2 * 1 + 495 * 3 * 2 + 385 * 4 * 3 + 315 * 8 * 4) mod 3465
= (1386 + 2970 + 4620 + 10,080) mod 3465
= 19056 mod 3465
= 1731
x = 1731

To Verify the answer: - x mod mi = ai
1731 mod 5 = 1
1731 mod 7 = 2
1731 mod 9 = 3
1731 mod 11 = 4