Cfrgtkky

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!

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}: xequiv 7equiv 18$. We notice that $18$ also satisfies $xequiv 3pmod{5}$.

So $xequiv 18 pmod{55}$.

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

Thus our solution is $xequiv 348pmod{385}$

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

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

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

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!

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}$