0
$\begingroup$

Problem

enter image description here


This may be a very easy question to answer but I can't seem to find a good source online explaining it. I want to know how they isolated for $j$. We can write $$7j+6\equiv 4 \text{ mod } 5$$ $$7j\equiv 3 \text{ mod } 5$$ and by the law of division for modular arithmetic we are allowed to divide both sides by $7$ since $gcd(7,5)=1$, which gives

$$j\equiv \dfrac{3}{7} \text{ mod } 5$$

So what did they do to change the remainder from $\dfrac{3}{7}$ to $4$?

Thanks


$\endgroup$
1
$\begingroup$

Note that $7j \equiv 2j \bmod 5$ so you want $2j\equiv 3\equiv 8$ (it is convenient that $5$ is odd so you know that adding once gives an even number). Then you can simply divide by $2$ since $5$ and $2$ have no common factor.

In general terms if you want to divide by $a$ modulo $p$ with $(a,p)=1$ you can find $b,c$ with $ab+pc=1$ (Euclid's algorithm will do this for you). This is the same as $ab\equiv 1 \bmod p$

So to solve $$aq\equiv r \bmod p$$ multiply by $b$ to get $$aqb=(ab)q\equiv q\equiv rb \bmod p$$

$\endgroup$
2
$\begingroup$

We have to figure out what is the inverse of $7$.

$$7\cdot 3 \equiv 21 \equiv 1 \pmod 5.$$

Hence $$7^{-1} \equiv 3 \pmod 5$$

$$7^{-1} \cdot 3 \equiv 3 \cdot 3 \equiv 9 \equiv 5+4 \equiv 4 \pmod{5}.$$

In general, to find the inverse for modulo arithmetic, we use Euclidean algorithm.

$\endgroup$
0
$\begingroup$

$$3≡3+5(5)≡28\bmod5$$ Now we can divide both sides by 7 and get $j≡4\bmod5$.

$\endgroup$

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.