Exercise · ZW-CHINESE-REMAINDER-THEOREM-007 · ★★☆ Intermediate
Solve \(x\equiv 1 \pmod 5\) and \(x\equiv 2 \pmod 7\). What is the smallest positive integer \(x\) satisfying both?
Choose one option.
Show answer
- B. \(16\)
Explanation
The number \(16\) satisfies \(16\equiv 1\pmod 5\) and \(16\equiv 2\pmod 7\). The option \(30\) satisfies the second congruence but not the first, since \(30\equiv 0\pmod 5\).
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-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-006 ZW-CHINESE-REMAINDER-THEOREM-008 →