The Chinese Remainder Theorem is used to solve a system of simultaneous congruences. It states that if n1, n2, n3 are pairwise relatively prime, then there exists a unique solution x to the system of congruences x ≡ a1 (mod n1), x ≡ a2 (mod n2), x ≡ a3 (mod n3) modulo M = n1n2n3. The document provides an example of using the Chinese Remainder Theorem to solve the system x ≡ 2 (mod 3), x ≡ 1 (mod 4), x ≡ 3 (mod 5), finding the solution to be x = 53 (mod 60).
The Chinese Remainder Theorem is used to solve a system of simultaneous congruences. It states that if n1, n2, n3 are pairwise relatively prime, then there exists a unique solution x to the system of congruences x ≡ a1 (mod n1), x ≡ a2 (mod n2), x ≡ a3 (mod n3) modulo M = n1n2n3. The document provides an example of using the Chinese Remainder Theorem to solve the system x ≡ 2 (mod 3), x ≡ 1 (mod 4), x ≡ 3 (mod 5), finding the solution to be x = 53 (mod 60).
Original Description:
An easy approach to knowing about Chinese Remainder Theorem.
The Chinese Remainder Theorem is used to solve a system of simultaneous congruences. It states that if n1, n2, n3 are pairwise relatively prime, then there exists a unique solution x to the system of congruences x ≡ a1 (mod n1), x ≡ a2 (mod n2), x ≡ a3 (mod n3) modulo M = n1n2n3. The document provides an example of using the Chinese Remainder Theorem to solve the system x ≡ 2 (mod 3), x ≡ 1 (mod 4), x ≡ 3 (mod 5), finding the solution to be x = 53 (mod 60).
The Chinese Remainder Theorem is used to solve a system of simultaneous congruences. It states that if n1, n2, n3 are pairwise relatively prime, then there exists a unique solution x to the system of congruences x ≡ a1 (mod n1), x ≡ a2 (mod n2), x ≡ a3 (mod n3) modulo M = n1n2n3. The document provides an example of using the Chinese Remainder Theorem to solve the system x ≡ 2 (mod 3), x ≡ 1 (mod 4), x ≡ 3 (mod 5), finding the solution to be x = 53 (mod 60).
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 10
The Chinese Remainder
Theorem Solve x 2mod3 x 1mod4 x 3mod5 Tell me the characteristics of x. x 2mod3 x 1mod4 x 3mod5 M = 345=60 M 1 = 60/3 = 20 M 2 = M 3 = M 1 = 20 m 1 = 3 Solve 20x 1 1 mod3 2x 1 1 mod3 x 1 = M 2 = 15 m 2 = 4 Solve 15x 2 1 mod4 3x 2 1 mod4 x 2 = M 3 = 12 m 3 = 5 Solve 12x 3 1 mod5 2x 3 1 mod5 x 3 = X = b 1 M 1 x 1 +b 2 M 2 x 2 +b 3 M 3 x 3 =2(20)(2)+1(15)(3)+3(12) (3)=233mod60 53mod60 So a! "ositive ite#er co#r$et to 53 mod 60 is a sol$tio to the s!stem Example o Tr! "ol#e x2 mod3 x3mod5 x2mod% Sol$tio x=23323mod105 $ome%or& '( ime permis) loo& a exer*ise 35 on pa+e 5,- Read se*ion 2-3 Exer*ises 33 a*e ((o hand in)) 35 (noe ha all m i are relai#el! prime- .o/ *an sho% ha some o( he *on+r/en*es are red/ndan and *an here(ore be eliminaed-)
