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$
  • 2
    $\begingroup$ Not quite. If $x \equiv 8 \pmod{9}$, then $6x \equiv 3 \pmod{9}$. $\endgroup$ – user61527 Sep 27 '13 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$ – Numbersandsoon Sep 27 '13 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$ – Numbersandsoon Sep 27 '13 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 Sep 27 '13 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 Sep 27 '13 at 6:59
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$
  • $\begingroup$ I have no idea what you did there. My idea was to reduce the system to one where the CRT is applicable. $\endgroup$ – Numbersandsoon Sep 27 '13 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 Sep 27 '13 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$
  • 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 Feb 5 '14 at 12:51

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.