Exercise · ZW-CHINESE-REMAINDER-THEOREM-006 · ★★☆ Intermediate
Solve \(x\equiv 2 \pmod 3\) and \(x\equiv 3 \pmod 4\). What is the least positive residue of \(x\) modulo \(12\)?
Choose one option.
Show answer
- C. \(11\)
Explanation
The number \(11\) satisfies \(11\equiv 2 \pmod 3\) and \(11\equiv 3 \pmod 4\), and since it is less than \(12\) it is the residue sought. The option \(7\) does not leave remainder \(2\) when divided by \(3\).
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-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?
- 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-005 ZW-CHINESE-REMAINDER-THEOREM-007 →