[Math] Does a system om congruence equations have solutions

chinese remainder theoremcongruencesdiscrete mathematics

I have a system of congruence equations

$$
\begin{cases}
x \equiv 17 \pmod{15} \\
x \equiv 14 \pmod{33}
\end{cases}
$$

I need to investigate the system and see if they've got any solutions.

I know that I should use the Chinese remainder theorem "in a reverse order" so I think I should split each congruence equation in two new systems of two congruence equations.

From the CRT two congruence equations can be joined in a single congruence equation by

$$
x \equiv b_1 + c n_1 (b_2 – b_1) \pmod{n_1 n_2}
$$

From the first congruence equation I can get these two
$$
b_1 + c n_1 (b_2 – b_1) = 17 \\
n_1 n_2 = 15
$$

and from the second I can get
$$
b_1 + cn_1 (b_2 – b_1) = 14 \\
n_1 n_2 = 33
$$

but the unknown variables are not combined so I cannot just solve the system of four equations.

I need a hint 🙂

Best Answer

$x\equiv2(\mod15)\implies x=15k+2$ for some integer $k$. Similarly $x=33m+14$.

Thus $15k+2=33m+14\implies15k-33m=12\implies5k-11m=4$.

$\gcd(5,11)=1$ so the equation above has solutions.

Related Question