3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user247327 Aug 18 '15 at 22:12
  • $\begingroup$ edited. thanks! $\endgroup$ – Rickz0rz Aug 18 '15 at 22:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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!! $\endgroup$ – Rickz0rz Aug 18 '15 at 22:18
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ very detailed. thank you!! $\endgroup$ – Rickz0rz Aug 18 '15 at 22:32
1
$\begingroup$

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

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