# Does a system om congruence equations have solutions?

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

• The first congruence implies $x=15k+17$ and the second one implies $x=33m+14$.Now equate the two expressions. – rah4927 Nov 27 '14 at 11:07
• @rah4927: Are you implying that you have a system of $2$ equations in $3$ variables, hence you can choose the value of one of the variables (in this case, either $k$ or $m$)? If yes, then you seem to ignore the fact that they all have to be integers, so it's not that simple. – barak manos Nov 27 '14 at 11:15
• @barakmanos,no,I meant that by equating the two expressions($15k+17=33m+14$),we can see that a solution exists by Bezout's identity. – rah4927 Nov 27 '14 at 11:26

## 3 Answers

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

• why do you write $x \equiv 2 \pmod{15}$ instead of $x \equiv 17 \pmod{15}$? I know that $17 \pmod{15} = 2$ but why can I just replace $17$ with $2$? – Jamgreen Nov 27 '14 at 11:48
• You conclude that the equation has solutions because $\text{gcd}(5,11) = 1$. What should be the two numbers gcd for a system with no solutions? – Jamgreen Nov 27 '14 at 11:51
• The answer to the first question is simply modular arithmetic. And I did not get your second question. Can you restate it kindly? – Landon Carter Nov 27 '14 at 11:53
• Okay :-) If I had another system with no solutions I would use the same method as you did but with values different from 5 and 11. What could be two values from which I can conclude that this system has no solutions? In the system from my question which do have solutions you conclude that it has solutions because $\text{gcd}(5,11) = 1$ so I just wonder what the result should be for a system without no solutions – Jamgreen Nov 27 '14 at 11:57
• Can you tell if the system $x=8(\mod 12)$ and $x=6(\mod9)$ is solvable? If, why? If not, why? – Landon Carter Nov 27 '14 at 12:02

$\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]$

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