In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m.[1] In the standard notation of modular arithmetic this congruence is written as which is the shorthand way of writing the statement that m divides (evenly) the quantity ax − 1, or, put another way, the remainder after dividing ax by the integer m is 1.
denotes the multiplication of equivalence classes modulo m.[2] Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately.
As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form Finding modular multiplicative inverses also has practical applications in the field of cryptography, e.g. public-key cryptography and the RSA algorithm.
If d is the greatest common divisor of a and m then the linear congruence ax ≡ b (mod m) has solutions if and only if d divides b.
[7] A modular multiplicative inverse of an integer a with respect to the modulus m is a solution of the linear congruence The previous result says that a solution exists if and only if gcd(a, m) = 1, that is, a and m must be relatively prime (i.e. coprime).
Furthermore, when this condition holds, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique:[8] If b and b' are both modular multiplicative inverses of a respect to the modulus m, then therefore If a ≡ 0 (mod m), then gcd(a, m) = m, and a won't even have a modular multiplicative inverse.
When ax ≡ 1 (mod m) has a solution it is often denoted in this way − but this can be considered an abuse of notation since it could be misinterpreted as the reciprocal of
The notation would be proper if a is interpreted as a token standing for the congruence class
representing the operations on congruence classes, these definitions are and These operations are well-defined, meaning that the end result does not depend on the choices of representatives that were made to obtain the result.
The congruence classes of the integers modulo m were traditionally known as residue classes modulo m, reflecting the fact that all the elements of a congruence class have the same remainder (i.e., "residue") upon being divided by m. Any set of m integers selected so that each comes from a different congruence class modulo m is called a complete system of residues modulo m.[9] The division algorithm shows that the set of integers, {0, 1, 2, ..., m − 1} form a complete system of residues modulo m, known as the least residue system modulo m. In working with arithmetic problems it is sometimes more convenient to work with a complete system of residues and use the language of congruences while at other times the point of view of the congruence classes of the ring
[10] Not every element of a complete residue system modulo m has a modular multiplicative inverse, for instance, zero never does.
After removing the elements of a complete residue system that are not relatively prime to m, what is left is called a reduced residue system, all of whose elements have modular multiplicative inverses.
is the Euler totient function, i.e., the number of positive integers less than m that are relatively prime to m. In a general ring with unity not every element has a multiplicative inverse and those that do are called units.
The group of units of the ring of integers modulo m is called the multiplicative group of integers modulo m, and it is isomorphic to a reduced residue system.
The following example uses the modulus 10: Two integers are congruent mod 10 if and only if their difference is divisible by 10, for instance Some of the ten congruence classes with respect to this modulus are: The linear congruence 4x ≡ 5 (mod 10) has no solutions since the integers that are congruent to 5 (i.e., those in
Since gcd(3, 10) = 1, the linear congruence 3x ≡ 1 (mod 10) will have solutions, that is, modular multiplicative inverses of 3 modulo 10 will exist.
The represented congruence classes form the group of units of the ring
These congruence classes are precisely the ones which have modular multiplicative inverses.
A modular multiplicative inverse of a modulo m can be found by using the extended Euclidean algorithm.
Then, using a method called "back substitution", an expression connecting the original parameters and this gcd can be obtained.
In other words, integers x and y can be found to satisfy Bézout's identity, Rewritten, this is that is, so, a modular multiplicative inverse of a has been calculated.
In big O notation, this algorithm runs in time O(log2(m)), assuming |a| < m, and is considered to be very fast and generally more efficient than its alternative, exponentiation.
As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverses.
× if and only if a is coprime to m. Therefore, a modular multiplicative inverse can be found directly: In the special case where m is a prime,
Some disadvantages of this method include: One notable advantage of this technique is that there are no conditional branches which depend on the value of a, and thus the value of a, which may be an important secret in public-key cryptography, can be protected from side-channel attacks.
[12] The basic idea is to form the product of all the ai, invert that, then multiply by aj for all j ≠ i to leave only the desired a−1i.
In particular, in the RSA algorithm, encrypting and decrypting a message is done using a pair of numbers that are multiplicative inverses with respect to a carefully selected modulus.
Modular multiplicative inverses are used to obtain a solution of a system of linear congruences that is guaranteed by the Chinese Remainder Theorem.
For example, the system has common solutions since 5,7 and 11 are pairwise coprime.
Also, the modular multiplicative inverse figures prominently in the definition of the Kloosterman sum.