Modular multiplicative inverse
In modular arithmetic, the modular multiplicative inverse of an integer a modulo an integer m > 1 is an integer b such that a b \equiv 1 \pmod{m}, meaning m divides a b - 1 but not necessarily a or b.[1] Such an inverse exists if and only if a and m are relatively prime, that is, their greatest common divisor satisfies \gcd(a, m) = 1.[2] When it exists, the inverse is unique modulo m, and it enables "division" in the ring of integers modulo m by allowing multiplication by b to undo multiplication by a.[3] The existence of modular multiplicative inverses is a cornerstone of elementary number theory, directly tied to Bézout's identity, which states that \gcd(a, m) = 1 if and only if there exist integers x and y such that a x + m y = 1; here, x \pmod{m} is the inverse of a.[4] Computationally, the inverse is efficiently found using the extended Euclidean algorithm, which not only computes \gcd(a, m) but also yields the coefficients from Bézout's identity.[5] For prime moduli p, every nonzero a modulo p has an inverse, forming the multiplicative group \mathbb{Z}_p^\times, and Fermat's Little Theorem provides a method to compute it as a^{p-2} \pmod{p}.[6] Modular inverses play a vital role in applications beyond pure mathematics, particularly in cryptography, where they are essential for constructing secure systems like the RSA algorithm. In RSA, the private decryption exponent d is the modular multiplicative inverse of the public encryption exponent e modulo \phi(n), where n is the product of two large primes and \phi is Euler's totient function, allowing efficient decryption while keeping the factorization of n secret.[7] They also underpin elliptic curve cryptography and other protocols by facilitating scalar multiplication and point decompression in finite fields.[8]Modular Arithmetic Basics
Congruences and Equivalence Classes
In modular arithmetic, two integers a and b are said to be congruent modulo n, where n is a positive integer, denoted a \equiv b \pmod{n}, if n divides the difference a - b.[9] This relation is an equivalence relation on the set of integers, satisfying reflexivity (a \equiv a \pmod{n}), symmetry (if a \equiv b \pmod{n}, then b \equiv a \pmod{n}), and transitivity (if a \equiv b \pmod{n} and b \equiv c \pmod{n}, then a \equiv c \pmod{n}).[9] The equivalence relation partitions the integers into equivalence classes, known as residue classes modulo n. The residue class of a modulo n, denoted _n, consists of all integers b such that b \equiv a \pmod{n}, or equivalently, _n = \{a + kn \mid k \in \mathbb{Z}\}. There are exactly n distinct residue classes modulo n, typically represented by the integers $0, 1, \dots, n-1.[10] Congruences support basic arithmetic operations: if a \equiv b \pmod{n} and c \equiv d \pmod{n}, then a + c \equiv b + d \pmod{n} and a \cdot c \equiv b \cdot d \pmod{n}. These operations are well-defined on the set of residue classes, allowing arithmetic to be performed modulo n without altering equivalence.[11] The set of residue classes modulo n, denoted \mathbb{Z}/n\mathbb{Z}, forms a commutative ring under these addition and multiplication operations, with the additive identity $0 \pmod{n} and multiplicative identity $1 \pmod{n}.[12]Greatest Common Divisor in Modular Contexts
In modular arithmetic, the greatest common divisor (GCD) of two integers a and n, where n > 0, plays a crucial role in determining the structure of solutions to equations within the ring of integers modulo n. The Euclidean algorithm provides an efficient method to compute \gcd(a, n) by leveraging the division algorithm repeatedly. Specifically, the algorithm states that \gcd(a, n) = \gcd(n, a \mod n), and it proceeds by replacing a with n and n with the remainder a \mod n until the remainder is zero; the last non-zero remainder is the GCD.[13] This process terminates because the remainders form a strictly decreasing sequence of non-negative integers. If the algorithm terminates with a GCD of 1, then a and n are coprime.[14] For an illustrative example, consider computing \gcd(15, 28): \begin{align*} 28 &= 1 \cdot 15 + 13, \\ 15 &= 1 \cdot 13 + 2, \\ 13 &= 6 \cdot 2 + 1, \\ 2 &= 2 \cdot 1 + 0. \end{align*} The last non-zero remainder is 1, so \gcd(15, 28) = 1, indicating that 15 and 28 are coprime.[15] Bézout's identity further connects the GCD to linear combinations: if d = \gcd(a, n), then there exist integers x and y such that a x + n y = d. Moreover, the set of all integer linear combinations of a and n consists precisely of the multiples of d.[16] A proof sketch relies on the Euclidean algorithm's steps, using back-substitution to express the GCD as such a combination. Starting from the base case where the remainder is d (with previous remainder 0), substitute backwards through the division steps. For instance, in the example above for \gcd(15, 28) = 1: \begin{align*} 1 &= 13 - 6 \cdot 2, \\ 2 &= 15 - 1 \cdot 13 \quad \Rightarrow \quad 1 = 13 - 6 \cdot (15 - 1 \cdot 13) = 7 \cdot 13 - 6 \cdot 15, \\ 13 &= 28 - 1 \cdot 15 \quad \Rightarrow \quad 1 = 7 \cdot (28 - 1 \cdot 15) - 6 \cdot 15 = 7 \cdot 28 - 13 \cdot 15. \end{align*} Thus, x = -13 and y = 7 satisfy $15(-13) + 28(7) = 1. This back-substitution works generally because each remainder is a linear combination of the originals, propagating the expression upwards.[16][17] Two integers a and n are defined as coprime if \gcd(a, n) = 1. In the context of congruences, which equate integers differing by multiples of the modulus, coprimality has significant implications for solvability. Specifically, the linear congruence a x \equiv b \pmod{n} is solvable for x if and only if \gcd(a, n) divides b; when \gcd(a, n) = 1, the congruence is always solvable for any b, with exactly one solution modulo n.[18] This condition ensures that the coefficient a generates all residue classes modulo n when coprime, facilitating unique solutions in modular equations.Definition and Conditions
Formal Definition
In modular arithmetic, the modular multiplicative inverse of an integer a modulo n, where n > 1 is a positive integer, is an integer x satisfying the congruence a x \equiv 1 \pmod{n}.[19] This x is commonly denoted as x \equiv a^{-1} \pmod{n}.[19] Algebraically, this concept corresponds to the multiplicative inverse in the ring \mathbb{Z}/n\mathbb{Z} of integers modulo n, where a and its inverse x are elements whose product is the multiplicative identity $1 in the ring.[20] The relation is symmetric: if x is the modular multiplicative inverse of a modulo n, then a is the modular multiplicative inverse of x modulo n.[4]Existence Criteria
The existence of a modular multiplicative inverse for an integer a modulo n > 1 is determined by a fundamental condition in number theory: such an inverse exists if and only if \gcd(a, n) = 1. This criterion ensures that a and n are coprime, meaning they share no common prime factors other than 1. When this holds, there exists an integer x such that a x \equiv 1 \pmod{n}.[21][22] To establish this theorem, consider the necessity first. Suppose an inverse x exists, so a x \equiv 1 \pmod{n}, which implies a x - n k = 1 for some integer k. Any common divisor of a and n must divide the left side a x - n k, hence it divides 1, forcing \gcd(a, n) = 1. For sufficiency, if \gcd(a, n) = 1, Bézout's identity guarantees integers x and y such that a x + n y = 1, or equivalently, a x \equiv 1 \pmod{n}. Thus, x serves as the inverse.[21][23] If \gcd(a, n) = d > 1, no inverse exists. In this case, d divides a, so for any integer x, a x \equiv 0 \pmod{d}. However, since d does not divide 1, a x \not\equiv 1 \pmod{d}, and thus a x \not\equiv 1 \pmod{n} because n is a multiple of d. This impossibility arises because the equation a x \equiv 1 \pmod{n} would require consistency modulo every divisor of n, including d.[24][25] This existence criterion extends to the broader solvability of linear congruences. The equation a x \equiv b \pmod{n} has solutions if and only if \gcd(a, n) divides b. When b = 1, this reduces to the inverse case, but the condition allows for solutions even when \gcd(a, n) > 1, provided the gcd divides b, with the number of distinct solutions modulo n then equaling the gcd value.[25][26]Properties and Uniqueness
Uniqueness of Inverses
When a modular multiplicative inverse exists for an integer a modulo n, it is unique modulo n. Specifically, if ax \equiv 1 \pmod{n} and ay \equiv 1 \pmod{n}, then x \equiv y \pmod{n}.[27] To prove this, subtract the congruences to obtain a(x - y) \equiv 0 \pmod{n}, meaning n divides a(x - y). Since the existence of the inverse requires \gcd(a, n) = 1, it follows that n divides (x - y), so x \equiv y \pmod{n}.[27] This uniqueness holds under the existence criterion that \gcd(a, n) = 1. The modular inverses modulo n exhibit several basic properties. First, the set of integers coprime to n (those possessing inverses) is closed under multiplication modulo n: if \gcd(a, n) = 1 and \gcd(b, n) = 1, then \gcd(ab \mod n, n) = 1.[28] Second, the inverse of an inverse recovers the original element: if b is the inverse of a modulo n, then the inverse of b is a modulo n. This follows because ab \equiv 1 \pmod{n} and, by commutativity of multiplication, ba \equiv 1 \pmod{n}, so a satisfies the defining congruence for the inverse of b.[27] Finally, the inverse of the negation -a modulo n is the negation of the inverse of a: if b is the inverse of a, then -b \mod n is the inverse of -a \mod n, since (-a)(-b) \equiv ab \equiv 1 \pmod{n}.[27]Connection to Units in Rings
In the ring \mathbb{Z}/n\mathbb{Z}, the units are the residue classes $$ where \gcd(a, n) = 1, as these are precisely the elements that admit multiplicative inverses under the ring's multiplication operation.[29] These units form a multiplicative subgroup known as the group of units, denoted U(n) or (\mathbb{Z}/n\mathbb{Z})^\times, consisting of all such invertible elements closed under multiplication modulo n.[30] The group U(n) is abelian, reflecting the commutative nature of multiplication in \mathbb{Z}/n\mathbb{Z}.[31] Its order is given by Euler's totient function \phi(n), which counts the number of integers from 1 to n-1 coprime to n.[30] Within this group structure, the modular multiplicative inverse of an element \in U(n) coincides with its group inverse [a^{-1}], satisfying \cdot [a^{-1}] = {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} in \mathbb{Z}/n\mathbb{Z}. As a consequence of group theory, this inverse is unique for each unit.[32] A key structural property arises from the Chinese Remainder Theorem: when n = pq with \gcd(p, q) = 1, the ring isomorphism \mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} induces a group isomorphism U(n) \cong U(p) \times U(q).[33] This decomposition allows inverses modulo n to be computed via separate inverses modulo p and q, combined using the theorem's reconstruction mechanism.[33]Computation Techniques
Extended Euclidean Algorithm
The extended Euclidean algorithm provides an efficient method to compute the modular multiplicative inverse of an integer a modulo n, assuming \gcd(a, n) = 1. This algorithm extends the standard Euclidean algorithm for finding the greatest common divisor by also determining integers x and y such that a x + n y = 1, based on Bézout's identity.[34] When \gcd(a, n) = 1, the value x \mod n serves as the modular inverse, since a x \equiv 1 \pmod{n}.[5] The algorithm proceeds in two phases. First, apply the Euclidean algorithm to compute \gcd(a, n) through successive divisions: divide n by a to get quotient q_1 and remainder r_1 = n - q_1 a, then a by r_1 to get q_2 and r_2 = a - q_2 r_1, and continue until the remainder is 1 (since the gcd is 1). This generates a sequence of equations expressing each remainder as a linear combination of a and n. In the second phase, back-substitute starting from $1 = r_k (the last non-zero remainder) upwards, substituting previous expressions to solve for x and y. The coefficients are updated iteratively: initialize s_0 = 1, s_1 = 0, then for each step i \geq 2, s_i = s_{i-2} - q_i s_{i-1}, where q_i is the quotient at that step; the final s_k gives x.[35][36] Consider the example of finding the inverse of 5 modulo 17. Apply the Euclidean algorithm:$17 = 3 \cdot 5 + 2,
$5 = 2 \cdot 2 + 1,
$2 = 2 \cdot 1 + 0.
Thus, \gcd(5, 17) = 1. Now back-substitute:
$1 = 5 - 2 \cdot 2,
but $2 = 17 - 3 \cdot 5, so
$1 = 5 - 2 \cdot (17 - 3 \cdot 5) = 5 - 2 \cdot 17 + 6 \cdot 5 = 7 \cdot 5 - 2 \cdot 17.
Hence, x = 7 and y = -2, and $5 \cdot 7 = 35 \equiv 1 \pmod{17}, confirming 7 as the inverse.[34][5] The following pseudocode implements the recursive version, returning the gcd d, x, and y:
To compute the inverse, callfunction extended_gcd(a, n): if n == 0: return a, 1, 0 d, s1, t1 = extended_gcd(n, a % n) s = t1 t = s1 - (a // n) * t1 return d, s, tfunction extended_gcd(a, n): if n == 0: return a, 1, 0 d, s1, t1 = extended_gcd(n, a % n) s = t1 t = s1 - (a // n) * t1 return d, s, t
extended_gcd(a, n); if d = 1, the inverse is s \mod n.[36]
The time complexity of the extended Euclidean algorithm is O(\log \min(a, n)), matching the standard Euclidean algorithm due to the logarithmic number of division steps.[37][38]
Euler's Theorem Method
Euler's theorem provides a method for computing the modular multiplicative inverse of an integer a modulo n when \gcd(a, n) = 1. The theorem states that if a and n are coprime, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi(n) is Euler's totient function.[39] From this congruence, it follows that a^{\phi(n) - 1} \equiv a^{-1} \pmod{n}, since multiplying both sides by a^{-1} (which exists under the coprimality condition) yields the identity.[19] To apply this method, first compute \phi(n), defined as \phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right), where the product is over the distinct prime factors p of n.[40] Then, calculate a^{\phi(n) - 1} \mod n using efficient modular exponentiation algorithms, such as binary exponentiation, which reduces the computational complexity to O(\log(\phi(n))) multiplications modulo n.[19] This approach leverages the group structure of the units modulo n, whose order is \phi(n), but focuses practically on exponentiation rather than group-theoretic operations.[41] For example, consider finding the inverse of 3 modulo 10. Since \gcd(3, 10) = 1 and \phi(10) = 10 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 4, compute $3^{4-1} = 3^3 = 27 \equiv 7 \pmod{10}. Verifying, $3 \times 7 = 21 \equiv 1 \pmod{10}, confirming that 7 is the inverse.[40][19] While theoretically elegant due to its connection to the totient function, this method can be inefficient for large n without optimized exponentiation, as \phi(n) may still be substantial and require factorization of n upfront.[41] It remains valuable for theoretical analysis and cases where exponentiation is preferred over other techniques.[42]Illustrative Examples
Basic Numerical Examples
To illustrate the concept of a modular multiplicative inverse, consider the case of finding the inverse of 7 modulo 26. Since \gcd(7, 26) = 1, an inverse exists, and using the extended Euclidean algorithm yields 15 as the solution, as $7 \times 15 = 105 \equiv 1 \pmod{26}.[43] To verify, compute the product and reduce: $105 \div 26 = 4 remainder 1, confirming $105 \equiv 1 \pmod{26}. In contrast, the integer 4 has no modular multiplicative inverse modulo 6, because \gcd(4, 6) = 2 \neq 1. This violates the existence condition, rendering the congruence $4x \equiv 1 \pmod{6} unsolvable for any integer x, as the greatest common divisor does not divide 1.[4] For small moduli, the inverses of numbers coprime to the modulus can be tabulated systematically. The following table lists the modular multiplicative inverses modulo 5 (where \gcd(a, 5) = 1 for a = 1, 2, 3, 4):| a | a^{-1} \pmod{5} | Verification |
|---|---|---|
| 1 | 1 | $1 \times 1 = 1 \equiv 1 \pmod{5} |
| 2 | 3 | $2 \times 3 = 6 \equiv 1 \pmod{5} |
| 3 | 2 | $3 \times 2 = 6 \equiv 1 \pmod{5} |
| 4 | 4 | $4 \times 4 = 16 \equiv 1 \pmod{5} |