0
$\begingroup$

I'm trying to follow this example on solving systems of congruences to understand CRT, however I do not understand how the author solves the following congruence:

$$ 7j + 6 \equiv 4 \pmod 5 \\ j \equiv 4 \pmod 5 $$

If I were to attempt to solve this congruence, I would try $$ 7j + 6 \equiv 4 \pmod 5 \\ 7j \equiv -2 \pmod 5 $$ but I do not know if subtracting 6 from both sides is valid.

Assuming it is, I would just guess and check numbers until I found a $j$ such that $5|(7j + 2)$.

So how do I solve this congruence (ideally, without guessing and checking)?

$\endgroup$
2
$\begingroup$

We have $$7j+6\equiv 4\bmod 5,$$ subtracting $6$ gives $$7j\equiv -2\equiv 3\bmod 5,$$ that is $$2j\equiv3\bmod 5.$$ Now we must find a number $b$ such that $2b\equiv 1\bmod 5$ in order to isolate $j$. It can be checked that $b=3$ does the trick. So, multiplying the congruence through by $3$ gives $$j\equiv 9\equiv 4\bmod 5.$$

$\endgroup$
  • 1
    $\begingroup$ Just to make sure I understand, you go from $7j \equiv -2 \pmod 5$ to $7j \equiv 3 \pmod 5$ by adding 5 to the right-hand side, which you can do because that's like adding 0 when dealing with regular equations? $\endgroup$ – Charles German Jun 2 '18 at 1:42
  • 1
    $\begingroup$ indeed - in general; $a\equiv b\bmod n$ and $a\equiv b+kn\bmod n$ are the same. in this case, these two statements are equivalent: "a number has a remainder of $-2$ when divided by $5$" and "a number has a remainder of $3$ when divided by $5$. $\endgroup$ – thesmallprint Jun 2 '18 at 1:55

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.