Design and Analysis of Algorithms20815 marksNumerical: Chinese Remainder TheoremSolving Modular Linear Equations, Chinese Remainder Theorem,
Solve the following linear equation using Chinese Remainder Theorem. x = 1 MOD 3,x = 2 MOD 5,x = 0 MOD 7
Solve the following linear equation using Chinese Remainder Theorem. x = 1 MOD 3,x = 2 MOD 5,x = 0 MOD 7 [5]
$$x \equiv 1 \pmod{3}, \quad x \equiv 2 \pmod{5}, \quad x \equiv 0 \pmod{7}$$ $i$ remainder $ai$ modulus $mi$ --------- 1 1 3 2 2 5 3 0 7 Check coprimality: $\gcd(3,5)=\gcd(5,7)=\gcd(3,7)=1$. Moduli are pairwise coprime, so CRT gives a unique solution mod $M$. Product of moduli: $$M = 3 \times 5 ...