Exercise · ZW-CHINESE-REMAINDER-THEOREM-003 · ★☆☆ Basic

If \(x\equiv a \pmod{m}\) and \(x\equiv b \pmod{n}\) with \(\mathrm{gcd}(m,n)=1\), which congruence describes all solutions?

Choose one option.

Show answer
  • B. \(x\equiv x_0 \pmod{mn}\), where \(x_0\) satisfies both congruences

Explanation

The congruence describing all solutions has modulus \(mn\) and is the single class satisfying both conditions. The option with modulus \(m+n\) and product \(ab\) does not match the theorem.

Study Elementary number theory in ZWMath →

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-002 ZW-CHINESE-REMAINDER-THEOREM-004 →