# solving negative linear congruences

OK so I know how to solve linear congruences when they're positive but negative is a different story..

I have $$200x\equiv 13 \pmod {1001}$$

I got the inverse as $$-5$$ and then I multiply both sides with the inverse to get:

$$-1000x \equiv -65 \pmod {1001}$$

So $$x \equiv -65 \mod {1001}$$

Is that correct? I tried to perform a check by substituting it back in the equation but it won't work :(

Thanks!

• There's an obvious error where you say that you have found the inverse of 200 to be -5 and then say "I multiply both sides with the inverse to get – user247327 Aug 18 '15 at 22:12
• edited. thanks! – Rickz0rz Aug 18 '15 at 22:17

Notice that if you multiply by $5$ on both sides, you can get rid of the $200$ very quickly and save yourself the trouble of having to use the extended Euclidean algorithm. Also, your mistake is not having a negative sign on both sides of your congruence.

$200x \equiv 13 \pmod{1001} \Rightarrow 1000x \equiv 65 \pmod{1001} \Rightarrow -x \equiv 65 \pmod{1001}$.

Now, multiply both sides by $-1$:

$x \equiv -65 \pmod{1000} \equiv 936 \pmod{1001}$

• ahh makes sense now. that negative was confusing me. I meant to write 65 in the original post btw. but after that I was lost as to how to get x. it was quite straight forward. thank you!! – Rickz0rz Aug 18 '15 at 22:18

You should get $-1000x\equiv -65$ when you multiply both sides by $-5$ which is the same as $x\equiv -65\equiv 936$

Check: $200 \times 936= 187200\equiv 87100\equiv 7020 \equiv 13$ where the multiples of $1001$ deducted at each stage are $100100, 80080, 7007$

You could also note that $1001=7\times 11\times 13$ so you could solve $200y \equiv 5 \bmod 77$ or $46y\equiv 5$ with $x=13y$. It happens that this is no easier, but it could come in handy in similar cases. It works because the equivalence modulo $1001$ amounts to $$200x=13+1001n$$ for some integer $n$. $13$ divides the right-hand side so must be a factor of the left, so $x=13y$ for some integer $y$ and $13$ cancels throughout.

• very detailed. thank you!! – Rickz0rz Aug 18 '15 at 22:32

Start with $$1001-5\cdot200=1$$ Multiply by $13$ to get $$13\cdot1001-65\cdot200=13$$ Therefore, $$200\,(-65)\equiv13\pmod{1001}$$ so $x\equiv-65\equiv936\pmod{1001}$.