In ordinary arithmetic, the multiplicative inverse of a nonzero number a is 1/a. In modular arithmetic, the multiplicative inverse of a modulo n is an integer x satisfying ax ≡ 1 (mod n). A modular inverse exists if and only if the greatest common divisor of a and n is 1. When the inverse exists, it is unique modulo n. The extended Euclidean algorithm is a standard method for finding it. For example, the inverse of 3 modulo 7 is 5 because 3 × 5 = 15 ≡ 1 (mod 7). Not every integer has a modular inverse: 2 has no inverse modulo 6 because gcd(2, 6) = 2. Modular inverses are essential for solving modular equations and performing division-like operations in modular systems.
Modular Inverses
A modular inverse of an integer a modulo n is an integer x whose product with a is congruent to 1 modulo n. Such an inverse exists exactly when a and n are relatively prime.
a x ≡ 1 (mod n) ⇔ gcd(a, n) = 1 for an inverse to exist
Explanation
Variables
A
The integer whose modular inverse is required.
X
A modular inverse of a modulo n.
N
The positive modulus.
Gcd(a, n)
The greatest common divisor of a and n.
Example or application
Problem
Find the multiplicative inverse of 4 modulo 9.
Solution
We need an integer x such that 4x ≡ 1 (mod 9). Testing x = 7 gives 4 × 7 = 28 = 3 × 9 + 1. Therefore, 4 × 7 ≡ 1 (mod 9).
Answer
The inverse of 4 modulo 9 is 7.
Text
The multiplicative inverse allows a factor to be cancelled from a congruence only when that factor is relatively prime to the modulus. Modular division is therefore not always possible.
Key Points
A modular inverse satisfies ax ≡ 1 (mod n).
An inverse exists exactly when gcd(a, n) = 1.
A modular inverse is unique modulo n when it exists.
The extended Euclidean algorithm can calculate modular inverses.
Modular division requires multiplication by an existing inverse.
An integer may have no inverse for a particular modulus.
Applications
Solving linear congruences.
RSA cryptographic calculations.
Finite-field arithmetic.
Modular division in computational mathematics.
Cryptographic key generation and related algorithms.
Learning Outcomes
Define a modular multiplicative inverse.
Determine whether an inverse exists using the greatest common divisor.
Find simple modular inverses.
Explain the role of the extended Euclidean algorithm.
Practice Questions
Find the inverse of 3 modulo 11.
Determine whether 6 has an inverse modulo 15.
Find the inverse of 7 modulo 10.
Explain why 2 has no inverse modulo 8.
Use the extended Euclidean algorithm to find the inverse of 17 modulo 43.
Related Concepts
Greatest Common Divisor
Extended Euclidean Algorithm
Linear Congruences
Modular Multiplication
Euler's Theorem
Common Mistakes
Assuming every nonzero integer has a modular inverse.
Checking whether a is nonzero instead of checking gcd(a, n) = 1.
Confusing an ordinary reciprocal with a modular inverse.
Dividing both sides of a congruence without verifying that the inverse exists.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- David M. Burton, Elementary Number Theory
Suggest a correction or source · More in Arithmetic & Number Theory