Question

Find the inverse for 43 modulo 660

Answer 1

We're looking for $x$ such that

$43x\equiv1\mod{660}$

so for some integer $n$ we can write

$43x+660n=1$

Apply Euclid's algorithm:

$660=43(15)+15$
$43=15(2)+13$
$15=13(1)+2$
$13=2(6)+1$
$\implies(660,43)=(43,15)=(15,13)=(13,2)=1$

From this we have

$1=13-2(6)$
$\implies1=-6(15)+7(13)$
$\implies1=-20(15)+7(43)$
$\implies1=-20(660)+307(43)$
$\implies(-20(660)+307(43))\equiv307(43)\equiv1\mod{660}$

which means 307 is the inverse of 43 modulo 660.