Design and Analysis of Algorithms20795 marksNumerical: Chinese Remainder TheoremSolving Modular Linear Equations, Chinese Remainder Theorem,
Solve the following linear congruences using Chinese Remainder Theorem.x≡1(mod2),x≡3(mod5),x≡6(mod7)x \equiv 1 \pmod{2},\quad x \equiv 3 \pmod{5},\quad x \equiv 6 \pmod{7}x≡1(mod2),x≡3(mod5),x≡6(mod7)
Solve the following linear congruences using Chinese Remainder Theorem.x≡1(mod2),x≡3(mod5),x≡6(mod7)x \equiv 1 \pmod{2},\quad x \equiv 3 \pmod{5},\quad x \equiv 6 \pmod{7}x≡1(mod2),x≡3(mod5),x≡6(mod7) [5]
$$x \equiv 1 \pmod{2}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$$ Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ Moduli: $m1 = 2,\ m2 = 5,\ m3 = 7$ The moduli are pairwise coprime, so a unique solution exists modulo their product. --- $$M = 2 \times 5 \times 7 = 70$$ --- $$M1 = 70/2 = 35, \quad...