Does a system om congruence equations have solutions?

1.1k Views Asked by At

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 :-)

3

There are 3 best solutions below

9
On

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

0
On

$ \left\{ \begin{array}{l} x \equiv 17\left[ {15} \right] \\ x \equiv 14\left[ {33} \right] \\ \end{array} \right. \Rightarrow x \equiv 47\left[ {495} \right] $

0
On

$$x\equiv17\pmod{15}\equiv2$$

$$\implies x\equiv2\pmod3\ \ \ \ (1),$$

$$x\equiv2\pmod5\ \ \ \ (2)$$

$$x\equiv14\pmod{33}\implies x\equiv14\pmod3\equiv2,$$

$$x\equiv14\pmod{11}\equiv3\ \ \ \ (3)$$

Now apply CRT on $(1),(2),(3)$ as $3,5,11$ are pairwise prime