In mathematics, in particular, the area of number theory, 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. In the standard notation of modular arithmetic this congruence is written as
Contents
- Modular arithmetic
- Integers modulo m
- Multiplicative group of integers modulo m
- Example
- Extended Euclidean algorithm
- Using Eulers theorem
- Applications
- References
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. If a does have an inverse modulo m there are an infinite number of solutions of this congruence which form a congruence class with respect to this modulus. Furthermore, any integer that is congruent to a (i.e., in a's congruence class) will have any element of x's congruence class as a modular multiplicative inverse. Using the notation of
where the symbol
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, i.e. public-key cryptography and the RSA Algorithm. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses.
In mathematical theory, assumptions about the properties of binary operators (for example the associative property and the commutative property) are often used as axioms in fields of study such as number theory and also two sub-disciplines of abstract algebra, group theory and ring theory.
Modular arithmetic
For a given positive integer m, two integers, a and b, are said to be congruent modulo m if m divides their difference. This binary relation is denoted by,
This is an equivalence relation on the set of integers, ℤ, and the equivalence classes are called congruence classes modulo m or residue classes modulo m. Let
A linear congruence is a modular equation of the form
Unlike linear equations over the reals, linear congruences may have zero, one or several solutions. If x is a solution of a linear congruence then every element in
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. If d divides b, then there are exactly d solutions.
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. Furthermore, when this condition holds, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique.
When ax ≡ 1 (mod m) has a solution it is often denoted in this way −
but this is an abuse of notation since a modular multiplicative inverse is an integer and, in general, a−1 is not an integer when a is. The notation would be proper if a is interpreted as a token standing for the congruence class
Integers modulo m
The congruence relation, modulo m, partitions the set of integers into m congruence classes. Operations of addition and multiplication can be defined on these m objects in the following way: To either add or multiply two congruence classes, first pick a representative (in any way) from each class, then perform the usual operation for integers on the two representatives and finally take the congruence class that the result of the integer operation lies in as the result of the operation on the congruence classes. In symbols, with
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 m congruence classes with these two defined operations form a ring, called the ring of integers modulo m. There are several notations used for these algebraic objects, most often
The congruence classes of the integers modulo m were traditionally known as residue classes, 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 is called a complete system of residues modulo m. 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
Multiplicative group of integers modulo m
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. The number of elements in a reduced residue system is
In a general ring with unity not every element has a multiplicative inverse and those that do are called units. As the product of two units is a unit, the units of a ring form a group, the group of units of the ring and often denoted by R× if R is the name of the ring. 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. In particular, it has order (size),
In the case that m is a prime, say p, then
Example
To illustrate the above definitions consider the following example using 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. In fact, 7 satisfies this congruence (i.e., 21 − 1 = 20). However, other integers also satisfy the congruence, for instance 17 and −3 (i.e., 3(17) − 1 = 50 and 3(−3) − 1 = −10). In particular, every integer in
is clearly divisible by 10. This congruence has only this one congruence class of solutions. The solution in this case could have been obtained by checking all possible cases, but systematic algorithms would be needed for larger moduli and these will be given in the next section.
The product of congruence classes
A complete residue system modulo 10 can be the set {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} where each integer is in a different congruence class modulo 10. The unique least residue system modulo 10 is {0, 1, 2, ..., 9}. A reduced residue system modulo 10 could be {1, 3, 7, 9}. The product of any two congruence classes represented by these numbers is again one of these four congruence classes. This implies that these four congruence classes form a group, in this case the cyclic group of order four, having either 3 or 7 as a (multiplicative) generator. The represented congruence classes form the group of units of the ring
Extended Euclidean algorithm
A modular multiplicative inverse of a modulo m can be found by using the extended Euclidean algorithm.
The Euclidean algorithm determines the greatest common divisor (gcd) of two integers, say a and m. If a has a multiplicative inverse modulo m, this gcd must be 1. The last of several equations produced by the algorithm may be solved for this gcd. 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. A more efficient version of the algorithm is the extended Euclidean algorithm, which, by using auxiliary equations, reduces two passes through the algorithm (back substitution can be thought of as passing through the algorithm in reverse) to just one.
In big O notation, this algorithm runs in time O(log(m)2), assuming | a | < m, and is considered to be very fast and generally more efficient than its alternative, exponentiation.
Using Euler's theorem
As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverses.
According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
where
In the special case where m is a prime,
This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:
Applications
Finding a modular multiplicative inverse has many applications in algorithms that rely on the theory of modular arithmetic. For instance, in cryptography the use of modular arithmetic permits some operations to be carried out more quickly and with less storage requirements, while other operations become more difficult. Both of these features can be used to advantage. 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. One of these numbers is made public and can be used in a rapid encryption procedure, while the other, used in the decryption procedure, is kept hidden. Determining the hidden number from the public number is considered to be computationally infeasible and this is what makes the system work to ensure privacy.
As another example in a different context, consider the exact division problem in computer science, 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 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.
- 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.