Discrete Structures20795 marksNumerical: Chinese remainder theoremApplications of Number Theory
Use Chinese remainder Theorem to find the value of x such that x = 0 (MOD 2), x = 2 (MOD 3), x = 3 (MOD 5).
Use Chinese remainder Theorem to find the value of x such that x = 0 (MOD 2), x = 2 (MOD 3), x = 3 (MOD 5). [5]
$$x \equiv 0 \pmod 2, \quad x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5$$ Moduli: $m1=2,\ m2=3,\ m3=5$. Residues: $a1=0,\ a2=2,\ a3=3$. $\gcd(2,3)=\gcd(2,5)=\gcd(3,5)=1$, so CRT applies. $$m = 2\times3\times5 = 30$$ $$M1=\frac{30}{2}=15,\quad M2=\frac{30}{3}=10,\quad M3=\frac{30}{5}=6$$ -