Chinese Remainder Theorem for non prime-numbers.

Question

Let's say I want to find x such that x leaves remainder 2 when divided by 3 and x leaves remainder 3 when divided by 5.
x % 3 = 2
x % 5 = 3
We break down the problem to:
x % 3 = 1
x % 5 = 0

Therefore,
5k % 3 = 1
2k % 3 = 1
k = 2
10, when remainder = 1
20, when remainder = 2

Now x % 3 = 0
and x % 5 = 1

3k % 5 = 1
k = 2
6, when remainder = 1
18, when remainder = 3

Therefore, final solution is 20 + 18 = 38.
38 is a solution
LCM of 3,5 = 15.
38 - 15 - 15 = 8.
8 is the least number, that is the solution.

But now if I have x % 7 = 3
x % 4 = 2

How do I solve the question ?

Answer 1

It has nothing to see with primeness of the moduli, but to their coprimeness. The systematic method consists in finding Bézout's coefficients for $7$ and $3$: $\enspace-1\cdot 7+2\cdot 4=1$ (For bigger numbers you can use the Extended Euclidean Algorithm).

The solution to the system of congruences \begin{equation*}\begin{cases}x\equiv 3 \pmod 7\\x\equiv 2 \pmod 4 \end{cases} \end{equation*} are then simply:$$x\equiv -2\cdot 7+3\cdot 2\cdot 4=10 \pmod{\operatorname{lcm(7,4)}}.$$

Answer 2

Exactly the same way. The equation $x\equiv 3 \mod 7$ tells you that $x=3+7y$ .

Plugging this into the second equation gives you $3+7y\equiv 2 \mod 4$, that is $-y\equiv -1 \mod 4$, so $y=1+4z$, and $x=10+28z$, i.e. $x\equiv 10 \mod 28$.