For integers and , a modular multiplicative inverse is a congruence class satisfying . It exists exactly when . Necessity follows because every common divisor of would divide . Conversely, Bézout's identity gives for coprime integers, making an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.
For example, , so . The modular congruence therefore has the unique solution class . Multiplication by sends all seventeen residue classes to different classes; multiplying by reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.
By contrast, has no modular inverse modulo . Its products have only residues . Consequently has no solution, while has five solution classes, . Dividing by a noninvertible residue would discard this distinction. In a prime field , every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.
If , the update satisfies because . For odd , starting with modulo and repeatedly doubling the number of correct bits computes its inverse modulo a power of two.
The computation of an integer satisfying . An inverse exists exactly when . The extended Euclidean algorithm produces such an from a Bezout identity .
For invertible residue classes , all their modular inverses can be recovered with one inversion and a linear number of multiplications. Store prefix products , invert once, and sweep backward: if the current inverse is , then and . The same construction works in any commutative group.
