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

  • $\begingroup$ The first congruence implies $x=15k+17$ and the second one implies $x=33m+14$.Now equate the two expressions. $\endgroup$ – rah4927 Nov 27 '14 at 11:07
  • $\begingroup$ @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. $\endgroup$ – barak manos Nov 27 '14 at 11:15
  • $\begingroup$ @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. $\endgroup$ – rah4927 Nov 27 '14 at 11:26

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

  • $\begingroup$ 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$? $\endgroup$ – Jamgreen Nov 27 '14 at 11:48
  • $\begingroup$ 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? $\endgroup$ – Jamgreen Nov 27 '14 at 11:51
  • $\begingroup$ The answer to the first question is simply modular arithmetic. And I did not get your second question. Can you restate it kindly? $\endgroup$ – Landon Carter Nov 27 '14 at 11:53
  • $\begingroup$ 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 $\endgroup$ – Jamgreen Nov 27 '14 at 11:57
  • $\begingroup$ Can you tell if the system $x=8(\mod 12)$ and $x=6(\mod9)$ is solvable? If, why? If not, why? $\endgroup$ – 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] $



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.