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.