Multiplicative inverse - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x⁻¹, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

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

Inverse function

In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

.

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

Euclid

Euclid , fl. 300 BC, also known as Euclid of Alexandria, was a Greek mathematician, often referred to as the "Father of Geometry". He was active in Alexandria during the reign of Ptolemy I...

's Elements
Euclid's Elements
Euclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...

.

In the phrase multiplicative inverse, the qualifier multiplicative is often omitted and then tacitly understood (in contrast to the additive inverse

Additive inverse

In mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero.The additive inverse of a is denoted −a....

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

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 another given element...

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⁻¹, the modular 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⁻¹ 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

0 (number)

0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...

does not have a reciprocal because no real number multiplied by 0 produces 1. With the exception of zero, reciprocals of every complex number

Complex number

A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

are complex, reciprocals of every real number

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

are real, and reciprocals of every rational number

Rational number

are rational. The imaginary unit

Imaginary unit

In mathematics, the imaginary unit allows the real number system ℝ to be extended to the complex number system ℂ, which in turn provides at least one root for every polynomial . The imaginary unit is denoted by , , or the Greek...

s, ±, are the only complex numbers with additive inverse

Additive inverse

In mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero.The additive inverse of a is denoted −a....

equal to multiplicative inverse. For example, additive and multiplicative inverses of are − = − and 1/ = −, 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 − 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 x ≠ 0. There must instead be given a rational number r such that 0 < r < |x|. In terms of the approximation algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

in the previous paragraph, this is needed to prove that the change in y will eventually become arbitrarily small.

In modular arithmetic

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

, 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

If and only if

In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

a and n are coprime

Coprime

In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

. For example, the inverse of 3 modulo 11 is 4 because 4 · 3 ≡ 1 (mod 11). The extended Euclidean algorithm

Extended Euclidean algorithm

The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...

may be used to compute it.

The sedenion

Sedenion

In abstract algebra, sedenions form a 16-dimensional non-associative algebra over the reals obtained by applying the Cayley–Dickson construction to the octonions...

s 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

If and only if

In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

its determinant

Determinant

In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

has an inverse in the coefficient ring

Ring (mathematics)

In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...

. 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 ƒ in the multiplicative sense, given by 1/ƒ, from the reciprocal or inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

with respect to composition, denoted by ƒ⁻¹ and defined by ƒ o ƒ⁻¹ = 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

French language

French is a Romance language spoken as a first language in France, the Romandy region in Switzerland, Wallonia and Brussels in Belgium, Monaco, the regions of Quebec and Acadia in Canada, and by various communities elsewhere. Second-language speakers of French are distributed throughout many parts...

, the inverse function is preferably called application réciproque).

A ring

Ring (mathematics)

in which every nonzero element has a multiplicative inverse is a division ring

Division ring

In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...

; likewise an algebra

Algebra (ring theory)

In mathematics, specifically in ring theory, an algebra over a commutative ring is a generalization of the concept of an algebra over a field, where the base field K is replaced by a commutative ring R....

in which this holds is a division algebra

Division algebra

In the field of mathematics called abstract algebra, a division algebra is, roughly speaking, an algebra over a field, in which division is possible.- Definitions :...

Pseudo-random number generation

The expansion of the reciprocal 1/q in any base can also act as a source of pseudo-random numbers, if q is a "suitable" safe prime

Safe prime

A safe prime is a prime number of the form 2p + 1, where p is also a prime. The first few safe primes are...

, 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 number

Irrational number

In mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....

s often can prove useful for reasons linked to the irrational number in question. Examples of this are the reciprocal of e

E (mathematical constant)

The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...

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

Golden ratio

In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...

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+√(n²+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

Zero divisor

In abstract algebra, a nonzero element a of a ring is a left zero divisor if there exists a nonzero b such that ab = 0. Similarly, a nonzero element a of a ring is a right zero divisor if there exists a nonzero c such that ca = 0. An element that is both a left and a right zero divisor is simply...

(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 sedenion

Sedenion

In abstract algebra, sedenions form a 16-dimensional non-associative algebra over the reals obtained by applying the Cayley–Dickson construction to the octonions...

s provide a counterexample.

The converse does not hold: an element which is not a zero divisor

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:

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

is simply

Practical applications

Examples and counterexamples

Pseudo-random number generation

Reciprocals of irrational numbers

Further remarks

See also