Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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}$
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.
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}$.
