# Solving Simple Linear Congruence

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?

• You don't know how to confirm if $\, 2\cdot 7\equiv 5\pmod 9 \,$ is true? – Bill Dubuque Nov 3 '16 at 22:01
• 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? – A. Epstein Nov 3 '16 at 22:03
• Impossible to answer without knowing more details. – Bill Dubuque Nov 3 '16 at 22:05

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$.
• 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$ ? – A. Epstein Nov 3 '16 at 21:27