Example involving the Chinese Remainder Theorem 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!
 A: 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}$
A: 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}$.
A: 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!
A: This is not a general solution, just a solution based on your specific example.
$x \equiv 3 \pmod 5$
$ x \equiv 5 \pmod 7$
$ x \equiv 7 \pmod{11}$
First notice that
$x+2  \equiv 0 \pmod 5$ and $ x+2 \equiv 0 \pmod 7$
Hence $x + 2 \equiv 0 \pmod{35}$. That is to say, $x = 35n - 2$ for some integer, $n$.
So \begin{align}
   35n - 2 &\equiv 7 \pmod{11} \\
   2n &\equiv 9 \pmod{11} \\
   2n &\equiv -2 \pmod{11} \\
   n &\equiv -1 \pmod{11}
\end{align}
So $n = 11m - 1$ and $x = 35(11m -1) - 2 = 385m - 37$
S0 $x \equiv -37 \equiv 348 \pmod{385}$
