# System modular equation.

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.

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

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

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

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

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.

• The only solution for it is: 2? – user180834 Jan 9 '15 at 23:19
• to modularity 12, yes. In the integers, 2, 14, 26, etc. – Joffan Jan 9 '15 at 23:22
• 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} $$– user180834 Jan 9 '15 at 23:25 • Please somebody confirm it. – user180834 Jan 9 '15 at 23:32 • 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. – Joffan Jan 9 '15 at 23:37 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.$$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)$.