# Solve the system of congruences

The system of congruences are as follows: $$3x \equiv 2 \, \text{mod 4}\\ 4x \equiv 1 \, \text{mod 5}\\ 6x \equiv 3 \, \text{mod 9}$$

Now, the idea is to of course find the inverse of each congruence and reduce it to a form where the Chinese Remainder Theorem can be applied: $$3x \equiv 1 \, \text{mod 4} \ \Leftrightarrow x \equiv 3 \, \text{mod 4}$$ i.e. the inverse of $3$ modulo $4$ is $3$. Also, $$4x \equiv 1 \, \text{mod 5} \ \Leftrightarrow x \equiv 4\, \text{mod 5}$$ i.e. the inverse of $4$ modulo $5$ is $4$. But with the last congruence, $(6,9)=3$ and so $6$ doesn't have an inverse modulo $9$. Does this mean the system of congruences does not have a solution?

• Not quite. If $x \equiv 8 \pmod{9}$, then $6x \equiv 3 \pmod{9}$. – user61527 Sep 27 '13 at 6:17
• True. Any way to find that inverse other than inspection? And besides using the Euclidean Algorithm.. And why does $(6,9)=3$ not decide that there is no solutions? – Numbersandsoon Sep 27 '13 at 6:23
• So writing $6x \equiv 3$ mod 9 as the equation $6x-9y=3$, we see a solution is $x=-1$ and $y=-1$, so that $x=-1 \equiv 8$ mod 9 is equivalent to $6x \equiv 3$ mod 9. Is this correct? – Numbersandsoon Sep 27 '13 at 6:41
• @BoSchmidt You are correct, also $6\cdot(9n+8) = 54n+48= 54n+ 9\cdot 5 + 3 = 9(6n+5)+3$ – Rustyn Sep 27 '13 at 6:47
• @BoSchmidt Since $4,5,9$ are pairwise coprime, there is a solution as guaranteed by the CRT. There's no trouble with $(6,9) = 3$. – Rustyn Sep 27 '13 at 6:59

$x\equiv 6 \mod{4} \Longrightarrow$ $x=4k+6$ for $k\in \mathbb{Z}$
$4\cdot (4k+6) \equiv 1 \mod{5} \Longrightarrow (4k+6)\equiv 4 \mod{5} \Longrightarrow$
$4k\equiv 3 \mod{5} \Longrightarrow k\equiv 2\mod{5}$,

So $k=5m+2$ for $m\in \mathbb{Z}$
$6\cdot (5m+2) \equiv 3 \mod{9} \Longrightarrow 30m\equiv 0\mod 9 \Longrightarrow m=9t$ for $t\in \mathbb{Z}$
So $k= 45t+2 \Longrightarrow x=180t +14.$

Explicitly, $$x\equiv 14 \mod{180}$$ Should end up being your solution.

If you want to reduce the system and apply the CRT, the reduced system is: \begin{align*} & x\equiv 3 \mod{4}\\ & x\equiv 4\mod{5}\\ &x \equiv 8\mod{9}\\ \end{align*} This is because, $6x\equiv 3 \mod{9} \Longleftrightarrow x\equiv 8\mod{9}$.
Note that since $4,5,9$ are pairwise coprime, there is a solution guaranteed by the CRT.

• I have no idea what you did there. My idea was to reduce the system to one where the CRT is applicable. – Numbersandsoon Sep 27 '13 at 6:32
• @BoSchmidt If you want to reduce the system, realize that $6\times 8 \equiv 48 \equiv 3 \mod{9}$, i.e. read T.Bonger's comment. – Rustyn Sep 27 '13 at 6:38

The answer from Rustyn is almost correct. However, the condition $6x \equiv 3 \pmod 9$ is equivalent to $2x \equiv 1 \pmod 3$ which in turn is equivalent to $x \equiv 2 \pmod 3$. The eventual answer should be a congrunce modulo $60$

• It's true that $9$ divides $6x-3$ if and only if $3$ divides $2x-1$, so the approach suggested here will work. Perhaps more should be said about the "eventual answer... modulo $60$". – hardmath Feb 5 '14 at 12:51