1
$\begingroup$

Im give the equation $ 2x \equiv 5\pmod 9 $ and am told to solve for the linear congruence. I attempted to this with only the methods taught to me and no more so i cannot use Bezout's Identity or a Diophantine Equation. I can only use Extended Euclid's algorithm and use modular arithmetic from there.

My attempt:

GCD(2,9)

$ 9 = (2)4+1$ (Find GCD)

$1 = (1)9 -4(2)$ (Solve 1 in terms of 9 and 2)

$1 \equiv 9 -4(2) \pmod 9$ (Rewrite equivalence with new inverse)

$9-4 = 5 $ (Finding equivalent positive multiplicative inverse)

$(5)2x \equiv (5)5 \pmod 9 $ (Go back to original equation and multiply each side by the inverse)

$x = 25 \pmod 9$ (The left side becomes x because $5*2 \pmod 9 = 1$)

$x = 7$ (Result)

I cannot find a single calculator online that confirms this answer. Quite honestly different calculators are giving me different answers so I'm not even quite sure if mine is wrong or not. Is this right or is there something wrong in my steps?

$\endgroup$
  • $\begingroup$ You don't know how to confirm if $\, 2\cdot 7\equiv 5\pmod 9 \,$ is true? $\endgroup$ – Bill Dubuque Nov 3 '16 at 22:01
  • $\begingroup$ Wow @BillDubuque i cant believe i missed that, just didn't even think about that to be quite honest. So seeing that my answer is right why is it that no calculator online can confirm this for me? $\endgroup$ – A. Epstein Nov 3 '16 at 22:03
  • $\begingroup$ Impossible to answer without knowing more details. $\endgroup$ – Bill Dubuque Nov 3 '16 at 22:05
1
$\begingroup$

This particular example is quite easy: $$ 2x \equiv 5 \equiv -4\bmod 9 \implies x \equiv -2 \equiv 7 \bmod 9 $$ This is easy because we can just divide the two sides of $2x \equiv -4\bmod 9$ by $2$ since $\gcd(2,9)=1$.

Note that $2x \equiv -4\bmod 9$ means that $9$ divides $2x+4=2(x+2)$, and so $9$ divides $x+2$.

$\endgroup$
  • $\begingroup$ Thanks for the response! I think my teacher wants me to turn the negative inverse into a positive one i know its just a preference but i will be wrong if i don't do it with that restriction what would you have done? I also don't understand your steps really; I'm new to this and I don't see/understand the shortcuts. @lhf $\endgroup$ – A. Epstein Nov 3 '16 at 21:22
  • $\begingroup$ Did you do $ -4 * 5 = -20 $ and then went on to say $x \equiv -20 \pmod 9$ and then $ x \equiv -2(10) $ and then $ 10 \pmod 9 = 1 $ so $ x \equiv -2 \pmod 9 $ ? $\endgroup$ – A. Epstein Nov 3 '16 at 21:27

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.