Exercise · ZW-CHINESE-REMAINDER-THEOREM-010 · ★★★ Advanced
Solve the system \(x\equiv 2 \pmod 3\), \(x\equiv 3 \pmod 5\), \(x\equiv 2 \pmod 7\). What is the residue of \(x\) modulo \(105\)?
Choose one option.
Show answer
- C. \(23\)
Explanation
The number \(23\) satisfies \(23\equiv 2\pmod 3\), \(23\equiv 3\pmod 5\) and \(23\equiv 2\pmod 7\). The number \(38\) meets the congruences modulo \(3\) and \(5\) but not modulo \(7\), since \(38\equiv 3\pmod 7\).
Review the concept: Chinese remainder theorem
The Chinese remainder theorem states that a system of linear congruences with pairwise coprime moduli has a unique solution modulo the product of those moduli.
\[x \equiv a_i \pmod{m_i},\ i=1,\dots,k \Rightarrow x \equiv x_0 \pmod{m_1\cdots m_k}\]
More practice problems: chinese remainder theorem
- ZW-CHINESE-REMAINDER-THEOREM-001 What condition must the moduli m_1,dots,m_k satisfy to apply the Chinese remainder theorem?
- ZW-CHINESE-REMAINDER-THEOREM-002 What is the modulus of the system x≡ 1 pmod 2, x≡ 2 pmod 3, x≡ 4 pmod 5?
- ZW-CHINESE-REMAINDER-THEOREM-003 If x≡ a pmodm and x≡ b pmodn with gcd(m,n)=1, which congruence describes all solutions?
- ZW-CHINESE-REMAINDER-THEOREM-004 Which number between 0 and 11 satisfies x≡ 1 pmod 3 and x≡ 0 pmod 4?
- ZW-CHINESE-REMAINDER-THEOREM-005 How many distinct solutions modulo M=m_1m_2 does the system with coprime moduli m_1 and m_2 have?
- ZW-CHINESE-REMAINDER-THEOREM-006 Solve x≡ 2 pmod 3 and x≡ 3 pmod 4. What is the least positive residue of x modulo 12?
- ZW-CHINESE-REMAINDER-THEOREM-007 Solve x≡ 1 pmod 5 and x≡ 2 pmod 7. What is the smallest positive integer x satisfying both?
- ZW-CHINESE-REMAINDER-THEOREM-008 Solve x≡ 3 pmod 4 and x≡ 4 pmod 5. What is the residue of x modulo 20?