Question

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

Answer 1

Are you familiar with the extended euclidean algorithm?

Answer 2

umm kinda

Answer 3

First start with the idea that

43s = 1 (mod 660)

This is basically saying that 660 divides (or is a factor of 43s-1


So

660 | (43s - 1)

Answer 4

When we say 660 | (43s - 1), we mean that there is an integer k such that


660k = 43s - 1

Answer 5

ok

Answer 6

Now move the 43s term over and make that -1 positive


660k = 43s - 1


660k - 43s = -1


43s - 660k = 1

Answer 7

We now apply the euclidean algorithm:


660 = 15*43 + 15


43 = 2*15 + 13


15 = 1*13 + 2


13 = 6*2 + 1


This shows us that the GCD between the two is 1, but more importantly, is we can rewrite that last term of 1 in terms of 660 and 43

Answer 8

Now take each equation and isolate the remainders:


660 = 15*43 + 15 ------> 15 = 660 - 15*43


43 = 2*15 + 13 ------> 13 = 43 - 2*15


15 = 1*13 + 2 ------> 2 = 15 - 1*13


13 = 6*2 + 1 ------> 1 = 13 - 6*2

Answer 9

With me so far?

Answer 10

yesssss

Answer 11

Take 1 = 13 - 6*2 and replace the "2" with 15 - 1*13

We can do this because 2 = 15 - 1*13


So

1 = 13 - 6*2


1 = 13 - 6*(15 - 1*13)


1 = 13 - 6*15 + 6*13

Answer 12

Then simplify to get

1 = -6*15 + 7*13

Answer 13

okkk got that

Answer 14

Then replace each copy of "13" with 43 - 2*15 (this is possible since 13 = 43 - 2*15)


1 = -6*15 + 7*(43 - 2*15)


1 = -6*15 + 7*43 - 14*15


1 = 7*43 - 20*15

Answer 15

okkkkkkkkkkkkkk

Answer 16

Finally, replace "15" with 660 - 15*43 to get


1 = 7*43 - 20*15


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


1 = 7*43 - 20*660 + 300*43


1 = 307*43 - 20*660


So


307*43 - 20*660 = 1

Answer 17

okkkkkkkk

Answer 18

Now get it back into the original form we had it


307*43 - 20*660 = 1


-20*660 = 1 - 307*43


20*660 = 307*43 - 1


20*660 = 43*307 - 1


660 | (43*307 - 1)


43*307 = 1 (mod 660)


Therefore, s = 307 which tells us that the multiplicative inverse of 43 (mod 660) is 307 (mod 660)

Answer 19

okkkk yay

Answer 20

THANKSSSSSSSSS

Answer 21

you're welcome