Is this a correct solution to the linear congruence?

107 Views Asked by At

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$

2

There are 2 best solutions below

3
On BEST ANSWER

No, here goes something wrong. The inverse of 2 is 5 rather than -2.

You should compute the inverse by the Extended Euclidean algorithm or perhaps you can guess it in a simple case with small numbers like this one.

0
On

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