# Inverse of an integer modulo m

• Mar 3rd 2008, 03:28 PM
lisaak
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
• Mar 3rd 2008, 05:49 PM
mr fantastic
Quote:

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 $a = \frac{16n+1}{5}$ where n is an integer. It's not hard to see that n = 4 works and so a = 13.
• Mar 3rd 2008, 07:30 PM
mr fantastic
Quote:

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 $a = \frac{16n+1}{5}$ 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.

• Mar 4th 2008, 04:35 AM
lisaak
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
• Mar 4th 2008, 04:52 AM
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?
• Mar 4th 2008, 01:23 PM
mr fantastic
Quote:

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!