# Is it possible to solve this congruency system?

I need help to determine if this congruency system can be solved and if it can be solved how do I do it: $$\begin{cases}x\equiv2\text{ (mod 3)}\\ x\equiv4\text{ (mod 6)}\\ \end{cases}$$

I do know that from the system I obtain the following:

\begin{align} x\equiv2\text{ (mod 3)}\\ x\equiv4\text{ (mod 2)}\\ x\equiv4\text{ (mod 3)}\\ \end{align}

I do not know what to conclude from here. I think this system doesn't have solution, but if it is so how do I prove it.

• kind of like a regular system of equations with $x=2$ and $x=4$ – J. W. Tanner Jun 26 '19 at 23:52

Doesn't have solution, since $$\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 4 \pmod{3} \end{cases}$$ they implie $$2\equiv 4 \pmod{3}$$, but this is false.

• @DavidG.Stork Not true, why do you believe that? The answer is fine as written. – Gone Jun 27 '19 at 2:16
• @DavidG.Stork It seems you may be confusing congruences with remainders. See e.g. here for the definitions. – Gone Jun 27 '19 at 3:51

$$x=6k+4\implies x=3(2k+1)+1$$

Thus if $$x\equiv 4\pmod {6}$$ then $$x\equiv 1\pmod 3$$

That is the system

$$\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 4 \pmod{3} \end{cases}$$

is not consistent.

\begin{align} {\bf Hint}\qquad\ \ \ 2+3j &= x = 4 + 6k\,\Rightarrow\ 3\,j-6\,k = 2\,\Rightarrow\, 3\mid 2,\,\ \rm contradiction.\\[.5em] {\rm generally}\ \ \ a+mj &= x = b + nk\,\Rightarrow\, \color{#c00}mj-\color{#c00}nk = b-a\,\Rightarrow\, \bbox[6px,border:1px solid #c00]{\color{#c00}{\gcd(m,n)}\mid b-a }\end{align}

i.e.  they're consistent $$\!\iff\!$$ they become equivalent when reduced mod the $$\rm\color{#c00}{gcd}$$ of the moduli.

The above necessary condition for a solution to exist is also a sufficient condition. Furthermore, a system of congruences is solvable $$\iff$$ pairwise solvable as above.

$$6k+4=3y+2\implies y=k=-{2\over 3}$$ repeating every time k changes by 1 (y by 2) , which then means, they aren't integer solutions for k snd y.