# Solving Linear Congruences.

Question is -:

Solve the linear congruence $3x \equiv 4\left(mod\, \, \, \, 7\right)$, and find the smallest positive integer that is a solution of this congruence

My Approach-:

$3x \equiv 4\left(mod\, \, \, \, 7\right)$

$\Rightarrow x \equiv 3^{-1}\, \,4\left(mod\, \, \, \, 7\right)$

$3^{-1}$ means it is the multiplicative inverse of $3\, \,mod\, \,7$

multiplicative inverse of $3\, \,mod\, \,7$

$\Rightarrow 7=3*2+1$

$\Rightarrow 3=1*3+0$

$\Rightarrow 1=1*7+\left(-2\right)3$

thus $-2$ or $5$ is the inverse.

Thus i am getting

$\Rightarrow x \equiv 3^{-1}\, \,4\left(mod\, \, \, \, 7\right)$

$\Rightarrow x \equiv 20\left(mod\, \, \, \, 7\right)$

But in the solution they are multiplying the inverse $5$ to both sides and get equation as-:

$15 \,x \equiv20 \, \left(mod\,\,7\right)$

and then

$x \equiv 15x\,\equiv\,20\,\equiv\,\,6\,\left(mod\,\,7\right)$

The solution is given here

thanks!

• If you write your equation as $3x\equiv -3\pmod{7}$ the solution is clearly $x\equiv -1\equiv 6\pmod{7}$, there is no need to compute any explicit inverse. – Jack D'Aurizio Mar 23 '17 at 6:33
• @JackD'Aurizio sir, i know this method.i want to solve this question using the above mentioned method! – laura Mar 23 '17 at 6:34
• I guess your instructor just intended to prevent negative integers. So she chose to multiply the congruence by $5$. – Megadeth Mar 23 '17 at 6:36
• @EricClapton there is no harm in learning new concepts ! :) – laura Mar 23 '17 at 6:37
• It looks like you did pretty much the same thing. You both multiplied by the inverse of 3. The only thing I didn't see you do was actually find the smallest positive integer congruent to 20. – Mike Mar 23 '17 at 6:56

You're not wrong, when you write $x \equiv 3^{-1} 4$, then you have also multiplied both sides by the inverse of $3$. You're just using different notation.
writing this as a formal fraction we have $$x\equiv \frac{4}{3}\equiv \frac{11}{3}\equiv \frac{18}{3}\equiv 6\mod 7$$