Exercise · ZW-CHINESE-REMAINDER-THEOREM-002 · ★☆☆ Basic
What is the modulus of the system \(x\equiv 1 \pmod 2\), \(x\equiv 2 \pmod 3\), \(x\equiv 4 \pmod 5\)?
Choose one option.
Show answer
- C. \(30\)
Explanation
The modulus of the unique solution is the product of the moduli, here \(2\cdot3\cdot5=30\). The option giving \(10\) uses only two of the three moduli.
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-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?
- 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-001 ZW-CHINESE-REMAINDER-THEOREM-003 →