Discrete Structures20805 marksNumerical: Chinese remainder theoremApplications of Number Theory
Using Chinese remainder theorem solve the following congruences.x = 1 (MOD 3), x = 3 (MOD 5), x = 6 (MOD 7)
Using Chinese remainder theorem solve the following congruences.x = 1 (MOD 3), x = 3 (MOD 5), x = 6 (MOD 7) [5]
System of congruences: $$x \equiv 1 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$$ - Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ - Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ --- $3, 5, 7$ are distinct primes, so they are pairwise coprime. CRT guarantees a unique solution modulo their product. ...