0
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ Not quite. If $x \equiv 8 \pmod{9}$, then $6x \equiv 3 \pmod{9}$. $\endgroup$
    – user61527
    Commented Sep 27, 2013 at 6:17
  • $\begingroup$ 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? $\endgroup$ Commented Sep 27, 2013 at 6:23
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Sep 27, 2013 at 6:41
  • 1
    $\begingroup$ @BoSchmidt You are correct, also $6\cdot(9n+8) = 54n+48= 54n+ 9\cdot 5 + 3 = 9(6n+5)+3$ $\endgroup$
    – Rustyn
    Commented Sep 27, 2013 at 6:47
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Rustyn
    Commented Sep 27, 2013 at 6:59

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I have no idea what you did there. My idea was to reduce the system to one where the CRT is applicable. $\endgroup$ Commented Sep 27, 2013 at 6:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rustyn
    Commented Sep 27, 2013 at 6:38
1
$\begingroup$

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$

$\endgroup$
1
  • 2
    $\begingroup$ 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$". $\endgroup$
    – hardmath
    Commented Feb 5, 2014 at 12:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .