1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Scounged Jul 20 '15 at 16:41
  • 1
    $\begingroup$ You were trying to find the inverse of $2$, not $4$. $\endgroup$ – Mike Jul 20 '15 at 16:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My mistake is that the inverse should be -4 and not -2, right? $\endgroup$ – Julia Jul 20 '15 at 17:08
  • $\begingroup$ @Julia Yes $-4 \equiv 5 \mod 9$, so -4 is an inverse. $\endgroup$ – wythagoras Jul 20 '15 at 17:14
  • $\begingroup$ Thanks, I updated my question to include the correct solution. Is it correct now? @wythagoras $\endgroup$ – Julia Jul 20 '15 at 17:19
1
$\begingroup$

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

$\endgroup$

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.