Discrete Structures207610 marksNumerical: Chinese remainder theoremApplications of Number Theory
Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.
Find the value of x such that x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.[10]
$$x \equiv 1 \pmod 3,\quad x \equiv 1 \pmod 4,\quad x \equiv 1 \pmod 5,\quad x \equiv 0 \pmod 7$$ Moduli: $m1=3,\ m2=4,\ m3=5,\ m4=7$ Remainders: $a1=1,\ a2=1,\ a3=1,\ a4=0$ All pairs $(3,4),(3,5),(3,7),(4,5),(4,7),(5,7)$ have gcd $=1$, so a unique solution exists modulo $M$. $$M = 3\times4\times...