How would I go about finding a solution to the following system?
$x\equiv 1\text{ mod }12\ \ \ \ \ \ \text{(1)}\\x\equiv4\text{ mod }21\ \ \ \ \ \ \text{(2)}\\x\equiv18\text{ mod } 35\ \ \ \ \text{(3)}$
It is a problem because $\gcd(12,21,35)\neq1$.
I can solve the system without (3) as follows I think:
Write $(1)$ as $x\equiv 1\mod4,x\equiv1\mod3$, then $(2)$ reduces to $x\equiv 1\mod3, x\equiv4\mod21$, thus we can solve:
$x\equiv 1\mod12\\x\equiv4\mod7$
and using Euler's algorithm we find $x\equiv25\mod84$. So we now want to solve:
$x\equiv25\mod84\ \ \ \ \ \ \text{(4)} \\ x\equiv18\mod35\ \ \ \ \ \ \text{(5)}$
But now the same trick won't work, since converting $(5)$ to $x\equiv3\mod5,x\equiv6\mod7$ gives a problem in $(4)$, since 25 is not divisible by $6$. This would suggest the system has no solutions, but it does, since for example $193$ is a solution.
What did I do wrong?
Best Answer
HINT:
$x\equiv 1\pmod{12}\ \ \ \ \ \ \text{(1)}\implies x\equiv1\pmod3, x\equiv1\pmod4$
$x\equiv4\pmod{21}\ \ \ \ \ \ \text{(2)}\implies x\equiv4\pmod3\equiv1, x\equiv4\pmod7$
$x\equiv18\pmod{35}\ \ \ \ \text{(3)}\implies x\equiv3\pmod5, x\equiv 4\pmod7$
So, we need $x\equiv1\pmod3, x\equiv1\pmod4, x\equiv3\pmod5,x\equiv 4\pmod7$
which is equivalent to $x\equiv1\pmod{12}\ \ \ \ \ (5)$ and $x\equiv18\pmod{35}\ \ \ \ \ (6)$
Now, apply CRT on $(5),(6)$ as $(12,35)=1$