4
$\begingroup$

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

Please help me out ,where i am wrong!

thanks!

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Mar 23 '17 at 6:33
  • $\begingroup$ @JackD'Aurizio sir, i know this method.i want to solve this question using the above mentioned method! $\endgroup$ – laura Mar 23 '17 at 6:34
  • $\begingroup$ I guess your instructor just intended to prevent negative integers. So she chose to multiply the congruence by $5$. $\endgroup$ – Megadeth Mar 23 '17 at 6:36
  • $\begingroup$ @EricClapton there is no harm in learning new concepts ! :) $\endgroup$ – laura Mar 23 '17 at 6:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Mike Mar 23 '17 at 6:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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