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: Use the direct CRT formula \(x \equiv \sum_i a_i N_i y_i \pmod{N}\), where \(N = 105\), \(N_i = N / n_i\), and \(y_i\) is the inverse of \(N_i\) modulo \(n_i\).

Step 2: For \(n_1 = 3, a_1 = 1\): \(N_1 = 105/3 = 35\). Since \(35 \equiv 2 \pmod 3\), find \(y_1\) with \(2y_1 \equiv 1 \pmod 3\); \(y_1 = 2\) works since \(2 \times 2 = 4 \equiv 1 \pmod 3\).

Step 3: For \(n_2 = 5, a_2 = 2\): \(N_2 = 105/5 = 21\). Since \(21 \equiv 1 \pmod 5\), \(y_2 = 1\).

Step 4: For \(n_3 = 7, a_3 = 3\): \(N_3 = 105/7 = 15\). Since \(15 \equiv 1 \pmod 7\), \(y_3 = 1\).

Step 5: Combine: \(x \equiv a_1 N_1 y_1 + a_2 N_2 y_2 + a_3 N_3 y_3 = 1(35)(2) + 2(21)(1) + 3(15)(1) = 70 + 42 + 45 = 157 \pmod{105}\). Reducing, \(157 - 105 = 52\).

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