display | more...

In many number sets (e.g. the real numbers, the rational numbers, etc.), a number x has a multiplicative inverse, which is commonly denoted 1/x (or x-1, as noted by jm), when x0. Then x*(1/x)=1. This kind of multiplicative inverse is often referred to as the reciprocal. Mathematicians decided that the natural numbers should have multiplicative inverses as well, which are still within the bounds of the natural numbers, so let a and n be natural numbers such that gcd(a,n)=1 (the necessary condition for a to have a multiplicative inverse mod n). Then a natural number q is the multiplicative inverse of a iff a*q=1(mod n) and 0<q<n.

Consider n=15. Then the multiplicative inverses q of a=1,2,...,14 are:

1. 1
2. 8
3. (none)
4. 4
5. (none)
6. (none)
7. 13
8. 2
9. (none)
10. (none)
11. 11
12. (none)
13. 7
14. 14

Notice that, for example, gcd(3,15)=3, so there is no multiplicative inverse here. Also a*q=1(mod n) iff (n-a)*(n-q)=1(mod n).

Log in or register to write something here or to contact authors.