Modular inverse question

Question

I am trying to find the x $$113x\equiv 311 \mod 653$$ but using Euclidean algorithm I calculate until here $$(-152)(113)\equiv 1 \mod 653$$ This negative number is confusing me. How can I go further to find the inverse? Or how can I change $$x\equiv -152 \mod 653$$ so that there wouldn't be any negative number? Can I simplify the question using Chinese remainder theorem?

Answer 1

If x must not necessarily be an integer, we may write:

$654 ≡ 1 mod 653$

$311ˣ 654 ≡ 311 mod 653$

comparing this with congruence $113 x ≡ 311 mod 653$ we get

$ x =\frac{ 311ˣ654}{ 113}$