Thread: Inverse of an integer modulo m

Hi, I have a test tomorrow, and I have been trying for a very long time to figure out how to do this. Thank you in advance for any help you can give me.

This is the question:
Find the inverse of 5 modulo 16.

Please explain how to do this in steps. I already know the answer, I just don't know how to get it.
Thanks

Originally Posted by lisaak

Hi, I have a test tomorrow, and I have been trying for a very long time to figure out how to do this. Thank you in advance for any help you can give me.

This is the question:
Find the inverse of 5 modulo 16.

Please explain how to do this in steps. I already know the answer, I just don't know how to get it.
Thanks

First of all, 5 and 16 are relatively prime so 5 does have a multiplicative inverse mod 16.

By definition, you need to find the integer value of a such that 5a = 1 modulo 16.

One quick way here is to see that where n is an integer. It's not hard to see that n = 4 works and so a = 13.

Originally Posted by mr fantastic

First of all, 5 and 16 are relatively prime so 5 does have a multiplicative inverse mod 16.

By definition, you need to find the integer value of a such that 5a = 1 modulo 16.

One quick way here is to see that where n is an integer. It's not hard to see that n = 4 works and so a = 13.

And I guess you saw that n = -1 works too => a = -3. The multipicative inverse is not unique.

A link you might find helpful is this.

Okay, so what if the numbers are larger? How do I find the inverse of say 40 mod 81? Because this one is not easy to see as in the previous example.

a= (81n+1)/40

alright, here is what I'm thinking:
since 40x is congruent to 1 mod 81
40x-1=81y (y in Z)
40x+81z=1 (where z is -y)

So working the Euclidean Algorithm backwards I can express the equation as 1=81-40*2

So, 40(-2) is congruent to 1 mod 81

81+(-2)=79
Thus, 79 is the multiplicative inverse.

Does this make sense?

Originally Posted by lisaak

alright, here is what I'm thinking:
since 40x is congruent to 1 mod 81
40x-1=81y (y in Z)
40x+81z=1 (where z is -y)

So working the Euclidean Algorithm backwards I can express the equation as 1=81-40*2

So, 40(-2) is congruent to 1 mod 81

81+(-2)=79
Thus, 79 is the multiplicative inverse.

Does this make sense?

Well you got a correct answer so it looks good to me!