0
$\begingroup$

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.

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

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.

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.