# Thread:

1. ## 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

2. 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.

3. 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.

4. 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

5. 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?

6. 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!
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 2, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9404527544975281, "perplexity_flag": "head"}