Example involving the Chinese Remainder Theorem

Question

I am working on a Number Theory book and I have come across the following problem:

(Underwood Dudley 2nd Edition Section 5 Problem 3):

Solve the system:

x $\equiv 3(mod 5)$

x $\equiv 5(mod7)$

x $\equiv 7(mod11)$

I understand that I must use the Chinese Remainder theorem and I understand that the CRT states that if the GCD of these three numbers there exists a unique solution (mod 385), but my book gives me no instruction on how to go about finding this solution--other than cold hard calculation. Could I have some advice or direction on the method to solving this problem and the idea behind the method? Thank you!

Answer 1

Here's a method, sometimes called 'adding the modulus', that works fairly well for small moduli--I'll apply it to your problem:

Start with the congruence of the largest modulus, and as we go through each step, we watch for a number that satisfies any of the remaining congruences.:

$\pmod{11}: x\equiv 7\equiv 18$. We notice that $18$ also satisfies $x\equiv 3\pmod{5}$.

So $x\equiv 18 \pmod{55}$.

Then $\pmod{55}: x\equiv 18\equiv 73\equiv 128\equiv 183\equiv 238\equiv 293\equiv348 $. Here we notice that $348$ also satisfies $x\equiv 5\pmod{7}$.

Thus our solution is $x\equiv 348\pmod{385}$

Answer 2

Since $x\equiv -2$ both $\pmod5$ and $\pmod7$, it must be congruent to $-2\equiv 33 \pmod{35}$.

Since $x+2\equiv 0\pmod{35}$, and $x+2\equiv 9\pmod{11}$, we want to know what $n$ makes $35n\equiv 2n\equiv 9\pmod{11}$. We see that $n=10$ does the trick.

So the answer is $x\equiv 35\cdot10 -2 = 348\pmod{385}$.

Answer 3

Let $(a_1, a_2, a_3) = (3, 5, 7)$ and let $(n_1, n_2, n_3) = (5, 7, 11)$ and let: $$ x = c_1a_1 + c_2a_2 + c_3a_3 $$ We want to solve for the coefficients $c_i$ so that they have the following special property: $$ c_i \equiv \begin{cases} 1 \pmod {n_j} &\text{if } j = i \\ 0 \pmod {n_j} &\text{if } j \neq i \\ \end{cases} $$ If we can do this, then $x$ will automatically satisfy the system of congruences! For example, $x \equiv 5 \pmod 7$ because: \begin{align*} x &= 3c_1 + 5c_2 + 7c_3 \\ &\equiv 3(0) + 5(1) + 7(0) \pmod 7 \\ &\equiv 5 \pmod 7 \end{align*} So it remains to find these magical coefficients. I'll show you how to get $c_2$.

---

We want $c_2 \equiv 1 \pmod 7$ and $c_2 \equiv 0 \pmod 5$ and $c_2 \equiv 0 \pmod {11}$. From the last two conditions, we know that $55$ divides $c_2$. Now what multiple of $55$ would have a remainder of $1$ when divided by $7$? By inspection, notice that $-55 = (-8)7 + 1$ [if this step didn't jump out to you, you could use the Extended Euclidean Algorithm to find integers $u,v$ such that $55u + 7v = \gcd(55, 7) = 1$, then just take $c_2 = 55u$]. So we can take $c_2 = -55$.

---

Try to find the other two coefficients yourself!