# Is this a correct solution to the linear congruence?

I want to solve this linear congruence:

$$2x \equiv 5 \pmod{9}$$ Backward substitution: $$9 = 4 \cdot 2 + 1$$ $$4(-2) + 9 = 1$$ Therefore, the inverse is: $-2$

Now multiply the linear congruence with $-2$ $$(2)(-2)x \equiv (-2)5 \pmod{9}$$ $$x \equiv -10 \pmod{9}$$

So: $$x = 8 + 9k$$ for an integer $k$

EDIT:

With the answers given below, the solution is:

Therefore, the inverse is: $-4$

Now multiply the linear congruence with $-4$ $$(2)(-4)x \equiv (-4)5 \pmod{9}$$ $$x \equiv -20 \pmod{9}$$ $$x \equiv 7 \pmod{9}$$

So: $$x = 7 + 9k$$ for an integer $k$

• With $x=8$ we get $2x=16\equiv 7 \pmod{9}$, so something went wrong in your solution. This is why it's good to check solutions. – Scounged Jul 20 '15 at 16:41
• You were trying to find the inverse of $2$, not $4$. – Mike Jul 20 '15 at 16:42

• @Julia Yes $-4 \equiv 5 \mod 9$, so -4 is an inverse. – wythagoras Jul 20 '15 at 17:14
$$2x\equiv 5\pmod 9 \Longrightarrow 2x=9n + 5, n\in\mathbb Z$$ We can solve linear diophantine equation now, but LHS divides by $2$; hence, $$0\equiv 9n + 5 \equiv 1 \cdot n + 1\pmod 2\Longrightarrow n = 2m + 1, m\in\mathbb Z$$ So, $$2x=9(2m+1)+5\Longrightarrow x = 9m + 7$$
If you know that $2^{-1}\equiv 5 \pmod 9$, then it's much more simpler: $$5\cdot 2x\equiv 25\equiv 7\pmod 9\Longrightarrow x\equiv 7\pmod 9$$