How to calculate the modular inverse from the bezout coefficients?

Question

I have the following equation $$P = c \cdot w^{-1} \bmod m.$$The known values are $c = 1503, w = 444$ and $m = 821$. I really don't know, how to get $w^{-1}$ (solution says it's 723). I used the extended euclidean algorithm and got for the bezout coefficients $$1 = 189 \cdot 1503 + (-346) \cdot 821.$$But here I am get stucked. How can I now calculate $w^{-1}$? I searched for days and didn't find an answer yet. Can somebody can give me the steps of the calculation please?

Answer 1

Your approach is correct, but you need the coefficients for $w$ and $m$, not for $c$ and $m$ (i.e. you need the coefficients for the number you are trying to invert and the modulus).

In your case, you'll find

$$ 444 × ( −98 )+ 821 × 53 = 1 $$

So the inverse of $444$ mod 821 is -98, also known as 723 :)