Question

Find an inverse for 43 modulo 660. That is, find an integer s such that 43s=1(mod 660)

Answer 1

307 is an inverse of 43 mod 660

Explanation:

We know that given integers
`a` and
`n`, if
`gcd(a, n) = 1`, then
`a` has an inverse modulo
`n`, and using Euclidean algorithm we find an inverse of
`a` expressing 1 as a linear combination of
`a` and
`n` finding integers
`s` and
`t` such that
`as+nt =1`, in this case,
`s` is an inverse of
`a`, i.e.,
`as`≡
`mod`
`n.`

To find the inverse of 43 mod 600, we need to do two steps:

1. We need to calculate the Greatest Common Divisor of 660 and 43 (gcd(660, 43)) using the Euclidean algorithm and verify that gcd(a, n) = 1.

`660=43*15+15,\\43=15*2+13,\\15=13*1+2;\\13= 2*6+1,\\2=2*1+0`

which implies that gcd(660, 43)= 1 and so 660 and 43 are relatively prime.

2. Express 1 as a linear combination of 43 and 600.

We work backwards using the equations derived by applying the Euclidean algorithm, expressing each remainder as a linear combination of the associated divisor and dividend:

`1 = 13-2*6`

`1=13-(15-13)*6` substitute
`2 = 15-13`,

`1=7*13-6*15` by algebra

`1=7*(43-15*2)-6*15` substitute
`13 = 43-15*2`

`1=7*43-20*15` by algebra

`1=7*43-20(660-43*15)` substitute
`15 = 660-43*15`

`1=307*43-20*660` by algebra.

Thus 43*307=1+20*660, then by definition of congruence modulo 660, 43*307 ≡ 1 (mod 600) and therefore 307 is an inverse of 43 mod 660.