Answer to Question #309882 in Abstract Algebra for badshah

Question

Find the multiplicative inverse of 197 modulo 3000. Highlight each step clearly.

Answer 1

Euclid’s algorithm:

$3000=15\cdot 197+45\\197=4\cdot 45+17\\45=2\cdot 17+11\\17=11+6\\11=6+5\\6=5+1$

The inverse procedure:

$1=6-5=\left( 17-11 \right) -\left( 11-6 \right) =17-2\cdot 11+6=\\=\left( 197-4\cdot 45 \right) -2\left( 45-2\cdot 17 \right) +\left( 17-11 \right) =\\=197-6\cdot 45+5\cdot 17-11=\\=197-6\left( 3000-15\cdot 197 \right) +5\left( 197-4\cdot 45 \right) -\left( 45-2\cdot 17 \right) =\\=-6\cdot 3000+96\cdot 197-21\cdot 45+2\cdot 17=\\=-6\cdot 3000+96\cdot 197-21\left( 3000-15\cdot 197 \right) +2\left( 197-4\cdot 45 \right) =\\=-27\cdot 3000+413\cdot 197-8\cdot 45=\\=-27\cdot 3000+413\cdot 197-8\left( 3000-15\cdot 197 \right) =\\=-35\cdot 3000+533\cdot 197$

Then

$197\cdot 533=1\mathrm{mod}3000\Rightarrow 197^{-1}=533\mathrm{mod}3000$