I'm confused how to solve this. $x^2 \equiv$ 11 (mod 35).
I know you're to split it up into $x^2 \equiv$11 (mod 7) and $x^2 \equiv$ 11 (mod 5). This produces answers of $x^2 \equiv$ 1, 4 (mod 5) and $\equiv$ 2, 5 (mod 7).
What I don't get is the next line: $x\equiv a$(7)(3) + $b$(5)(3).
Where does the 3 come from? Out of thin air? Thanks.
On
Some people apply the Chinese Remainder Theorem as stated, but I find that unwieldy in many cases. You have four pairs of congruences to solve; I'll show you a good technique with one of them.
We want $x\equiv 4\pmod 5$, and $x\equiv 5\pmod 7$. We'll start with the first one: The number $4$ is congruent to $4$ modulo $5$, and adding any multiple of $5$ to it doesn't change that. Thus, we start adding multiples of $5$, and stop when we reach a number that satisfies the second congruence: $4, 9, 14, 19$. There, we found it. The number $19$ satisfies both congruences, and that's one solution, modulo $35$. You can find the other three in a similar manner.
If you had a third congruence to satisfy, you could take $19$, and if it wasn't the solution, start adding multiples of $35$ until you get the needed number.
We have $$3\equiv 7^{-1}\mod 5$$ and $$3\equiv 5^{-1}\mod 7$$
Therefore we have to multiply both residues with $3$