# changing remainder $\dfrac{3}{7}$ to $4$ in mod $5$

Problem

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

## 3 Answers

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.

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

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