Multiplicative inverse


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

In mathematics, a multiplicative inverse or reciprocal 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 a fraction a/b is b/a. 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 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; 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

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.

Examples and counterexamples

In the field of real numbers, Zero does not have a reciprocal because no real number multiplied by 0 produces 1. With the exception of zero, reciprocals of every complex number are complex, reciprocals of every real number are real, and reciprocals of every rational number are rational. The imaginary units, ±i, are the only complex numbers with additive inverse equal to multiplicative inverse. For example, additive and multiplicative inverses of i are −(i) = −i and 1/i = −i, respectively.

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 a is also defined: it is the number x such that ax ≡ 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 4 · 3 ≡ 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.

Pseudo-random number generation

The expansion of the reciprocal 1/q in any base can also act [2] as a source of pseudo-random numbers, if q is a "suitable" safe prime, a prime of the form 2p + 1 where p is also a prime. A sequence of pseudo-random numbers of length q − 1 will be produced by the expansion.

Reciprocals of irrational numbers

Every number excluding zero has a reciprocal, and reciprocals of certain irrational numbers often can prove useful for reasons linked to the irrational number in question. Examples of this are the reciprocal of e which is special because no other positive number can produce a lower number when put to the power of itself, and the golden ratio's reciprocal which, being roughly 0.6180339887, is exactly one less than the golden ratio and in turn illustrates the uniqueness of the number.

There are an infinite number of irrational reciprocal pairs that differ by an integer (giving the curious effect that the pairs share their infinite mantissa). These pairs can be found by simplifying n+√(n2+1) for any integer n, and taking the reciprocal.

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 Z, all integers except −1, 0, 1 provide examples; 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  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}.

See also

Notes

  1. ^ " In equall Parallelipipedons the bases are reciprokall to their altitudes". OED "Reciprocal" §3a. Sir Henry Billingsley translation of Elements XI, 34.
  2. ^ Mitchell, Douglas W., "A nonlinear random number generator with known, long cycle length," Cryptologia 17, January 1993, 55-62.

References

  • Maximally Periodic Reciprocals, Matthews R.A.J. Bulletin of the Institute of Mathematics and its Applications vol 28 pp 147–148 1992

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • multiplicative inverse — n. Math. RECIPROCAL (n. 2) …   English World dictionary

  • multiplicative inverse — noun (mathematics) one of a pair of numbers whose product is 1: the reciprocal of 2/3 is 3/2; the multiplicative inverse of 7 is 1/7 • Syn: ↑reciprocal • Topics: ↑mathematics, ↑math, ↑maths • Hypernyms: ↑ …   Useful english dictionary

  • multiplicative inverse — noun Date: 1958 an element of a mathematical set that when multiplied by a given element yields the identity element called also reciprocal …   New Collegiate Dictionary

  • multiplicative inverse — Math. reciprocal (def. 9). [1955 60] * * * …   Universalium

  • Modular multiplicative inverse — The modular multiplicative inverse of an integer a modulo m is an integer x such that That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to The multiplicative inverse of a modulo m exists if and only if …   Wikipedia

  • Inverse (mathematics) — Inverse is the opposite of something. This word and its derivatives are used greatly in mathematics, as illustrated below. * Inverse element of an element x with respect to a binary operation * with identity element e is an element y such that x… …   Wikipedia

  • Inverse function — In mathematics, if fnof; is a function from A to B then an inverse function for fnof; is a function in the opposite direction, from B to A , with the property that a round trip (a composition) from A to B to A (or from B to A to B ) returns each… …   Wikipedia

  • Inverse element — In abstract algebra, the idea of an inverse element generalises the concept of a negation, in relation to addition, and a reciprocal, in relation to multiplication. The intuition is of an element that can undo the effect of combination with… …   Wikipedia

  • Inverse trigonometric functions — Trigonometry History Usage Functions Generalized Inverse functions Further reading …   Wikipedia

  • Multiplicative group of integers modulo n — In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.