Multiplicative inverse

From Wikipedia, the free encyclopedia

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

In mathematics, a multiplicative inverse for a number x, denoted by 1⁄x or x −1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of x is also called the reciprocal of x. The multiplicative inverse of a fraction p⁄q is q⁄p. For the multiplicative inverse of a real number, divide 1 by the number. For example, the reciprocal of 5 is one fifth (1⁄5 or 0.2), and the reciprocal of 0.25 is 1 divided by 0.25, or 4. The reciprocal function, the function ƒ(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; geometrical quantities in inverse proportion 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 understood (in contrast to the additive inverse). Multiplicative inverses can be defined over many mathematical domains as well as numbers. In these cases it can happen that ab ≠; ba; then "inverse" typically implies that an element is both a left and right inverse.

Contents

[edit] Examples and counterexamples

Zero does not have a finite reciprocal, as no real number 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 i2 = −1 represent the only numbers with additive inverse equal to 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−xy2. 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 x ≠ 0. There must instead 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 become arbitrarily small.

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

The sedenions are an algebra in which every nonzero element has a multiplicative inverse, but which nonetheless has 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−1 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 ƒ in the multiplicative sense, given by 1⁄ƒ, from the reciprocal or inverse function with respect to composition, denoted by ƒ−1 and defined by ƒ o ƒ−1 = id. Only for linear maps are they strongly related (see above), while they are completely different for all other cases. The terminology difference reciprocal versus 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 in which every nonzero element has a multiplicative inverse is a division ring; likewise an algebra in which this holds is a 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:

  1. Use the extended Euclidean algorithm to compute k−1, the modular multiplicative inverse of k mod 2w, 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.
  2. 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 safe prime, a prime of the form 2p+1 where p is also a prime. A stream of random numbers of length q−1 will be produced by the decimal expansion.

[edit] Further remarks

If the multiplication is associative, an element x with a multiplicative inverse cannot be a zero divisor (meaning for some y, xy = 0 with neither x nor y equal to zero). To see this, it is sufficient to multiply the equation xy = 0 by the inverse of x (on the left), and then simplify using associativity. In the absence of associativity, the sedenions provide a counterexample.

The converse does not hold: an element which is not a zero divisor is not guaranteed to have a multiplicative inverse. Within the integers, the nonzero integers provide an example; they are not zero divisors nor do they have inverses 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. For, first observe that the map ƒ(x) = ax must be injective: ƒ(x) = ƒ(y) implies x = y:

\begin{align} ax &= ay &\quad \rArr &\quad & ax-ay &= 0 \\ & &\quad \rArr &\quad & a(x-y) &= 0 \\ & &\quad \rArr &\quad & a^{-1}a(x-y) &= 0 \\ & &\quad \rArr &\quad & x-y &= 0 \\ & &\quad \rArr &\quad & x &= y \end{align}

Distinct elements map to distinct elements, so the image consists of the same finite number of elements, and the map is necessarily surjective. Specifically, ƒ (namely multiplication by a) must map some element x to 1, ax = 1, so that x is an inverse for a.

The multiplicative inverse of a fraction \tfrac{a}{b} is simply \tfrac{b}{a}.

[edit] References

  1. ^ " In equall Parallelipipedons the bases are reciprokall to their altitudes". OED "Reciprocal" §3a. Sir Henry Billingsley translation of Elements XI, 34.
  • Maximally Periodic Reciprocals, Matthews R.A.J. Bulletin of the Institute of Mathematics and its Applications vol 28 pp 147–148 1992

[edit] See also