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$
  • $\begingroup$ Investigate using lcm(4,6) as the modular base. $\endgroup$ – Joffan Jan 9 '15 at 22:53
  • $\begingroup$ ok, so we get one equation? $\endgroup$ – user180834 Jan 9 '15 at 22:56
  • $\begingroup$ Either one or none, depending on the values. In this case, yes, you get one. $\endgroup$ – Joffan Jan 9 '15 at 22:58
  • $\begingroup$ so, the solution for that is: 12k+2 yes? $\endgroup$ – user180834 Jan 9 '15 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 '15 at 23:02
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$.

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1. Could you add $\ .... \iff x \equiv a\ (\mod \text{lcm} (m,n)\ )$ ? $\endgroup$ – orangeskid Jan 10 '15 at 0:49
  • $\begingroup$ @orangeskid It's a hint, so some things are left for the OP. $\endgroup$ – Bill Dubuque Jan 10 '15 at 0:57
  • $\begingroup$ Oh, OK, makes sense. $\endgroup$ – orangeskid Jan 10 '15 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The only solution for it is: 2? $\endgroup$ – user180834 Jan 9 '15 at 23:19
  • $\begingroup$ to modularity 12, yes. In the integers, 2, 14, 26, etc. $\endgroup$ – Joffan Jan 9 '15 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 '15 at 23:25
  • $\begingroup$ Please somebody confirm it. $\endgroup$ – user180834 Jan 9 '15 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 '15 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.$$

| cite | improve this answer | |
$\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)$.

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