Question

(a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm.

Show your steps.

Answer 1

Euclidean Algorithm:

$141=7\cdot 19+8$

$19=2\cdot 8+3$

$8=2\cdot 3+2$

$3=1\cdot 2+1$

We have:

$1= \mathbf{3}-\mathbf{2} \\ \ \ \ = \mathbf{3}-(\mathbf{8}-2\cdot \mathbf{3)} \\ \ \ \ =3\cdot \mathbf{3}-\mathbf{8} \\ \ \ \ =3\cdot (\mathbf{19}-2\cdot \mathbf{8})-\mathbf{8} \\ \ \ \ =3\cdot \mathbf{19}-7\cdot \mathbf{8} \\ \ \ \ =3\cdot \mathbf{19}-7\cdot (\mathbf{141}-7\cdot \mathbf{19}) \\ \ \ \ =52\cdot \mathbf{19}-7\cdot \mathbf{141}$

$1=52\cdot 19-7\cdot 141\equiv 52\cdot 19\mod 141$

Answer: $52$ .