0
$\begingroup$

Consider: $$\begin{cases} x\equiv 2 \mod 4 \\ x \equiv 2 \mod 6 \end{cases} $$ And we would like use Chinese remainder theorem but we can't because $\gcd(4,6) > 1$ How can I deal with it.

$\endgroup$
7
  • $\begingroup$ Investigate using lcm(4,6) as the modular base. $\endgroup$
    – Joffan
    Jan 9, 2015 at 22:53
  • $\begingroup$ ok, so we get one equation? $\endgroup$
    – user180834
    Jan 9, 2015 at 22:56
  • $\begingroup$ Either one or none, depending on the values. In this case, yes, you get one. $\endgroup$
    – Joffan
    Jan 9, 2015 at 22:58
  • $\begingroup$ so, the solution for that is: 12k+2 yes? $\endgroup$
    – user180834
    Jan 9, 2015 at 22:59
  • $\begingroup$ Yes, can you see why other values (other than 2 that is) will not satisfy the equivalences? $\endgroup$
    – Joffan
    Jan 9, 2015 at 23:02

5 Answers 5

5
$\begingroup$

A more systematic approach:

By the Chinese remainder theorem, $x \equiv 2 \mod 6$ is equivalent to $x$ being both $2 \mod 2$ and $2 \mod 3$. So we can write a system of three equations:

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

The first two equations are modulo powers of the same prime, so we have to check whether they are compatible; they are (if they were not, we could immediately deduce that there are no solutions). So the condition $x \equiv 2 \mod 2$ is superfluous, it is already implied by $x \equiv 2 \mod 4$. So we end up with the following system:

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

Now we have coprime numbers $4$ and $3$, so we can use the Chinese remainder theorem to finish and find the solution $x \equiv 2 \mod 12$.

$\endgroup$
2
$\begingroup$

$ \begin{array}{}{\bf Hint}\!\!\!\! &&x\equiv a\pmod{\!m}\\ &&x\equiv a\pmod{\!n}\end{array}\!\iff\, m,n\mid x\!-\!a\iff {\rm lcm}(m,n)\mid x\!-\!a$

$\endgroup$
3
  • $\begingroup$ +1. Could you add $\ .... \iff x \equiv a\ (\mod \text{lcm} (m,n)\ )$ ? $\endgroup$
    – orangeskid
    Jan 10, 2015 at 0:49
  • $\begingroup$ @orangeskid It's a hint, so some things are left for the OP. $\endgroup$ Jan 10, 2015 at 0:57
  • $\begingroup$ Oh, OK, makes sense. $\endgroup$
    – orangeskid
    Jan 10, 2015 at 1:15
1
$\begingroup$

Starting with $$\begin{cases} x\equiv 2 \mod 4 \\ x \equiv 2 \mod 6 \end{cases} $$ we can investigate whether these conditions can be combined. The shortest cycle that contains 4 and 6 is the lcm(4,6) = 12.

$x \equiv 2 \mod 4$ gives $x\equiv \{2,6 \text{ or } 10\} \mod 12$

$x \equiv 2 \mod 6$ gives $x\equiv \{2 \text{ or }8\} \mod 12$

Clearly only 2 can meet both conditions.

The combined condition is therefore $x \equiv 2 \mod 12$

If, instead we had been looking for, say, $$\begin{cases} x\equiv 3 \mod 4 \\ x \equiv 2 \mod 6 \end{cases} $$

there would have been no solutions.

$\endgroup$
7
  • $\begingroup$ The only solution for it is: 2? $\endgroup$
    – user180834
    Jan 9, 2015 at 23:19
  • $\begingroup$ to modularity 12, yes. In the integers, 2, 14, 26, etc. $\endgroup$
    – Joffan
    Jan 9, 2015 at 23:22
  • $\begingroup$ ok, and is it true? $$\begin{cases} 2x\equiv 4 \mod 8\\ x \equiv 2 \mod 6 \end{cases} \iff $$\begin{cases} x\equiv 2 \mod 4 \\ x \equiv 2 \mod 6 \end{cases} $$ $\endgroup$
    – user180834
    Jan 9, 2015 at 23:25
  • $\begingroup$ Please somebody confirm it. $\endgroup$
    – user180834
    Jan 9, 2015 at 23:32
  • $\begingroup$ Well, it is actually true that $2x \equiv 4 \mod 8 \implies x \equiv 2 \mod 4$, but division in modular numbers is not always straightforward. $\endgroup$
    – Joffan
    Jan 9, 2015 at 23:37
1
$\begingroup$

$x\equiv 2\pmod 4\implies x=2+4n$ for some $n\in\Bbb Z$. So,

$$2+4n\equiv 2\pmod 6 \implies 4n\equiv 0\pmod 6$$. If $m=4n$, then $6|m$, therefore $m=12k$ for some $k$, and therefore the solutions are:

$$x=2+12k, k\in\Bbb Z.$$

$\endgroup$
0
$\begingroup$

We can also approach this by dividing by the common factor. $$ \begin{align} x/2&\equiv1\pmod2\\ x/2&\equiv2\pmod3 \end{align}\tag{1} $$


If Luck is With Us

If we notice that these are the same as $$ \begin{align} x/2&\equiv-1\pmod2\\ x/2&\equiv-1\pmod3 \end{align}\tag{2} $$ we can immediately get the solution to be $$ x/2\equiv-1\pmod6\tag{3} $$ which is the same as $$ x\equiv-2\pmod{12}\tag{4} $$ or $$ x\equiv10\pmod{12}\tag{5} $$


Extended Euclidean Algorithm

If we don't notice a nice relationship as we did in $(2)$, then we can resort to the Extended Euclidean Algorithm. First we solve $$ \begin{align} x/2&\equiv1\pmod2\\ x/2&\equiv0\pmod3 \end{align}\tag{6} $$ and $$ \begin{align} x/2&\equiv0\pmod2\\ x/2&\equiv1\pmod3 \end{align}\tag{7} $$ and add twice a solution of $(7)$ to a solution of $(6)$.

Here we proceed as implemented in the Euclid-Wallis Algorithm to solve $3x+2y=1$:

$$ \begin{array}{r} &&1&2\\\hline 1&0&1&-2\\ 0&1&-1&3\\ 3&2&1&0\\ \end{array}\tag{8} $$ $(8)$ gives the solution $3(1)+2(-1)=1$. This says that $x/2=3(1)$ is $1\bmod2$ and so solves $(6)$. It also says that $x/2=2(-1)$ is $1\bmod3$ and so solves $(7)$. Adding twice the solution to $(7)$ to the solution of $(6)$ gives $$ x/2\equiv-1\pmod6 $$ as a solution to $(1)$ as we got in $(3)$, which leads to the solution in $(5)$.

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