Discrete Structures20755 marksNumerical: Chinese remainder theoremApplications of Number Theory
Find the values of x such that x = 1 (mod 5) and x = 2 (mod 7) using Chinese remainder theorem.
Find the values of x such that x = 1 (mod 5) and x = 2 (mod 7) using Chinese remainder theorem. [5]
$$x \equiv 1 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$ So $a1 = 1$, $m1 = 5$; $a2 = 2$, $m2 = 7$. $\gcd(5, 7) = 1$, so CRT gives a unique solution mod $m = 5 \times 7 = 35$. $$m = 35$$ $$M1 = \frac{35}{5} = 7, \qquad M2 = \frac{35}{7} = 5$$ Find $y1$ with $M1 y1 \equiv 1 \pmod{5}$: $$7 y1 \equiv 1 \pmod...