Multiplicative inverse

From Wikipedia, the free encyclopedia

The reciprocal function: y = 1/x. For every x except 0, y represents its multiplicative inverse.

In mathematics,multiplicative inverse of a number x, denoted 1/x or x ⁻¹, is the number which, when multiplied by x, yields 1. The multiplicative inverse of x is also called the reciprocal of x. One computes the multiplicative inverse of a (real) number by dividing 1 by the number. For example, the reciprocal of 5 is one fifth (1/5 or 0.2), the reciprocal of 0.25 is 1 divided by 0.25, or 4. The reciprocal function, the function f(x) that maps x to 1/x, is one of the simplest examples of a function which is self-inverse.

The term reciprocal was in common use at least as far back as the third edition of Encyclopaedia Britannica (1797) to describe two numbers whose product is 1; two figures in plane geometry are described as reciprocall in a 1570 translation of Euclid's Elements.^[1]

In the phrase multiplicative inverse, the qualifier multiplicative is often omitted and then tacitly self-understood (in contrast to the additive inverse). Multiplicative inverses can be defined over many mathematical domains as well as numbers; in the non-abelian case, "inverse" implies that an element is both a left and right inverse.

1 Examples and counter-examples
2 Practical applications
3 Pseudo-random number generation
4 Further remarks
5 References
6 See also

[edit] Examples and counter-examples

Zero does not have a reciprocal, as division by 0 is undefined hence there exists no number which when multiplied by 0 produces 1. Every complex number except zero has a reciprocal that is a complex number. If a number is real, then so is its reciprocal, and if it is rational, then so is its reciprocal. The two complex solutions to the equation $i 2 = - 1$ represent the only numbers whose additive inverse is also its multiplicative inverse. To approximate the reciprocal of x, using only multiplication and subtraction, one can guess a number y, and then repeatedly replace y with 2y−xy². Once the change in y becomes (and stays) sufficiently small, y is an approximation of the reciprocal of x.

In constructive mathematics, for a real number x to have a reciprocal, it is not sufficient that it be false that x = 0. Instead, there must be given a rational number r such that 0 < r < |x|. In terms of the approximation algorithm in the previous paragraph, this is needed to prove that the change in y will eventually get arbitrarily small.

In modular arithmetic, the multiplicative inverse of x is also defined: it is the number a such that (a·x) mod n = 1. However, this multiplicative inverse exists only if a and n are relatively prime. For example, the inverse of 3 modulo 11 is 4 because it is the solution to (3x) mod 11 = 1. The extended Euclidean algorithm may be used to compute the multiplicative inverse modulo of a number.

The sedenions are an algebra in which every nonzero element has a multiplicative inverse, but which has nonetheless divisors of zero, i.e. nonzero elements x,y such that xy=0.

A square matrix has an inverse if and only if its determinant has an inverse in the coefficient ring. The linear map that has the matrix A⁻¹ with respect to some base is then the reciprocal function of the map having A as matrix in the same base. Thus, the two distinct notions of the inverse of a function are strongly related in this case, while they must be carefully distinguished in the general case (see below).

The trigonometric functions are related by the reciprocal identity: the cotangent is the reciprocal of the tangent; the secant is the reciprocal of the cosine; the cosecant is the reciprocal of the sine.

It is important to distinguish the reciprocal of a function f in the multiplicative sense, given by 1/f, from the reciprocal or inverse function w.r.t. composition, rather denoted by f⁻¹, defined by f o f⁻¹ = id. Only for linear maps they are strongly related (see above), while they are completely different for all other cases. The terminology reciprocal vs inverse is not sufficient to make this distinction, since many authors prefer the opposite naming convention, probably for historical reasons (for example in French, the inverse function is preferably called application réciproque).

A ring or an algebra in which every nonzero element has a multiplicative inverse is called a division ring resp. division algebra.

[edit] Practical applications

The multiplicative inverse has innumerable applications in algorithms of computer science, particularly those related to number theory, since many such algorithms rely heavily on the theory of modular arithmetic. As a simple example, consider the exact division problem where you have a list of odd word-sized numbers each divisible by k and you wish to divide them all by k. One solution is as follows:

Use the extended Euclidean algorithm to compute k^-1, the multiplicative inverse of k mod 2^w, where w is the number of bits in a word. This inverse will exist since the numbers are odd and the modulus has no odd factors.
For each number in the list, multiply it by k^-1 and take the least significant word of the result.

On many machines, particularly those without hardware support for division, division is a slower operation than multiplication, so this approach can yield a considerable speedup. The first step is relatively slow but only needs to be done once.

[edit] Pseudo-random number generation

The decimal expansion of the reciprocal 1/q can also act as a source of pseudo-random numbers, if q is a “suitable” prime number. A stream of random numbers of length q - 1 will be produced by the decimal expansion if q is such that q = 2S + 1 where S is a Sophie Germain prime, such that both S and 2S + 1 are prime, with S being of the form 3, 9 or 11 mod 20. Thus “suitable” prime numbers q are 7, 23, 47, 59, 167, 179, etc (corresponding to S = 3, 11, 23, 29, 83, 89, etc.). The result is a stream of length q-1 digits (including leading zeros). So, for example, using q = 23 generates the random digits 0,4,3,4,7,8,2,6.....3,9,1,3

[edit] Further remarks

An element which has a multiplicative inverse cannot be a zero divisor if the multiplication is associative. To see this, it is sufficient to multiply the equation x y = 0 by the inverse of x (on the left), and then simplify using associativity. The sedenions provide a counter example.

Conversely, an element which is not a zero divisors needs not to have a multiplicative inverse. The nonzero integers provide an example. (They are not zero divisors but have no inverse in Z.) If the ring or algebra is finite, however, then all elements a which are not zero divisors do have a (left and right) inverse. This can be seen by observing that the map x→ax must be injective (ax=ay => a(x-y)=0 => x-y=0), thus surjective, thus there is x such that ax=1.