Question

Which one of the following options is the general solution(s) of the linear congruences \(x \equiv 1 \pmod{3}\), \(x \equiv 2 \pmod{5}\) and \(x \equiv 3 \pmod{7}\)?

• A. \(x \equiv 17 \pmod{105}\)
• B. \(x \equiv 23 \pmod{105}\)
• C. \(x \equiv 31 \pmod{105}\)
• D. \(x \equiv 52 \pmod{105}\)

Hint:

Build up the solution one modulus at a time, or apply the explicit Chinese Remainder Theorem combination formula.

Answer 1

The Correct Option is D

Step 1: Since \(3, 5, 7\) are pairwise coprime, the modulus of the combined solution is \(N = 3 \times 5 \times 7 = 105\).

Step 2: Start with \(x \equiv 1 \pmod{3}\), so write \(x = 1 + 3k\). Substitute into \(x \equiv 2 \pmod{5}\): \(1 + 3k \equiv 2 \pmod{5}\), so \(3k \equiv 1 \pmod{5}\). The inverse of \(3\) modulo \(5\) is \(2\), since \(3 \times 2 = 6 \equiv 1 \pmod{5}\). So \(k \equiv 2 \pmod{5}\), giving \(k = 2 + 5m\) and \(x = 1 + 3(2 + 5m) = 7 + 15m\).

Step 3: Substitute into \(x \equiv 3 \pmod{7}\): \(7 + 15m \equiv 3 \pmod{7}\). Since \(7 \equiv 0\) and \(15 \equiv 1 \pmod{7}\), this reduces to \(m \equiv 3 \pmod{7}\), so \(m = 3 + 7n\) and \(x = 7 + 15(3 + 7n) = 52 + 105n\).

Step 4: Check: \(52 = 51 + 1 \equiv 1 \pmod{3}\), \(52 = 50 + 2 \equiv 2 \pmod{5}\), \(52 = 49 + 3 \equiv 3 \pmod{7}\). All three congruences are satisfied.

\[\boxed{x \equiv 52 \pmod{105}}\]