We're looking for [tex]x[/tex] such that
[tex]43x\equiv1\mod{660}[/tex]
so for some integer [tex]n[/tex] we can write
[tex]43x+660n=1[/tex]
Apply Euclid's algorithm:
[tex]660=43(15)+15[/tex]
[tex]43=15(2)+13[/tex]
[tex]15=13(1)+2[/tex]
[tex]13=2(6)+1[/tex]
[tex]\implies(660,43)=(43,15)=(15,13)=(13,2)=1[/tex]
From this we have
[tex]1=13-2(6)[/tex]
[tex]\implies1=-6(15)+7(13)[/tex]
[tex]\implies1=-20(15)+7(43)[/tex]
[tex]\implies1=-20(660)+307(43)[/tex]
[tex]\implies(-20(660)+307(43))\equiv307(43)\equiv1\mod{660}[/tex]
which means 307 is the inverse of 43 modulo 660.
