Finding Inverse in modulus m

Question

I've been learning the Euclidean algorithm and came across this simple problem.

$101^{-1} (mod 203)$

So I attempted it as such:

$203 = 101(2) + 1$

So we got a gcd of 1, we can stop and do:

$1 = 203 - 101(2)$

And since it's mod 203, we have 101(2)

So shouldn't the answer be $2$? My textbook says it's $201$, help would be much appreciated, as this is confusing as ever.

Thanks.

Answer 1

Observe that

$$2\cdot101=202=-1\pmod{203}\implies (101)^{-1}=-2=201\pmod{203}$$

Or using the EA:

$$203=2\cdot101+1\implies1\cdot203+\color{red}{(-2)}\cdot101=1\implies $$

$$\implies101^{-1}=-2\pmod{203}=201\pmod{203}$$

Answer 2

Since $2\cdot101+1\equiv0\pmod{203}$, we have $$ 2\cdot101\equiv-1\pmod{203} $$ Multiplying by $-1$ gives $$ -2\cdot101\equiv1\pmod{203} $$ But $-2\equiv201\pmod{203}$. Therefore, $$ 201\cdot101\equiv1\pmod{203} $$ and this is exactly what $201\equiv101^{-1}\pmod{203}$ means.