Exercise · ZW-CHINESE-REMAINDER-THEOREM-008 · ★★☆ Intermediate
Solve \(x\equiv 3 \pmod 4\) and \(x\equiv 4 \pmod 5\). What is the residue of \(x\) modulo \(20\)?
Choose one option.
Show answer
- A. \(19\)
Explanation
The number \(19\) satisfies \(19\equiv 3\pmod 4\) and \(19\equiv 4\pmod 5\), and it is the only option that satisfies both. The option \(9\) satisfies the second but not the first, since \(9\equiv 1\pmod 4\).
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-009 A system with x≡ 0 pmod 6 and x≡ 1 pmod 4. Does it have a solution? Choose the correct statement.
← ZW-CHINESE-REMAINDER-THEOREM-007 ZW-CHINESE-REMAINDER-THEOREM-009 →