I'm given the equation $ 2x \equiv 5\pmod 9 $ and am told to solve for the linear congruence. I attempted 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?
1 Answer
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$.
