# Modular multiplicative inverse

A modular multiplicative inverse of an integer b modulo m is an integer b⁻¹ such that b·b⁻¹ ≡ 1 (mod m); it is the analog of division in modular arithmetic, the system of remainders formalized by [Carl Friedrich Gauss](https://www.edgepedia.org/carl-friedrich-gauss) in his *Disquisitiones Arithmeticae* of 1801.<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup><sup> • </sup><sup>[2](https://mathshistory.st-andrews.ac.uk/Extras/Gauss_Disquisitiones/)</sup> The inverse exists exactly when b and m share no common factor greater than 1, and efficient algorithms compute it in a number of steps proportional to the logarithm of the input, which is what makes it practical in cryptography and computer algebra.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup>

| Key fact | Detail |
|---|---|
| Definition | An integer b⁻¹ with b·b⁻¹ ≡ 1 (mod m); for example, the inverses of 1, 2, 3, and 4 modulo 5 are 1, 3, 2, and 4.<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup> |
| Existence | A nonzero integer b has an inverse modulo m if and only if gcd(b, m) = 1; 12 has no inverse mod 15 because gcd(15, 12) = 3, while 8 does because gcd(15, 8) = 1.<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup><sup> • </sup><sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup> |
| Standard algorithm | The extended Euclidean algorithm returns integers s, t with s·m + t·a = gcd(m, a); when the gcd is 1, t is the inverse of a mod m, in Θ(log a) steps.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup> |
| Exponentiation alternative | Euler's theorem gives b⁻¹ = b^(φ(m)−1) (mod m); for a prime modulus p this reduces to b^(p−2).<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup> |
| Cryptographic use | In RSA the private exponent d is the multiplicative inverse of the public exponent e modulo φ(n).<sup>[4](https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture12.pdf)</sup> |
| Library support | Python's built-in `pow` accepts a negative exponent with a modulus since version 3.8: `pow(38, -1, mod=97)` returns 23. GMP's `mpz_invert` computes the inverse and returns 0 if none exists.<sup>[5](https://docs.python.org/3/library/functions.html)</sup><sup> • </sup><sup>[6](https://gmplib.org/gmp-man-6.3.0.pdf)</sup> |

## Existence and uniqueness

Whether an inverse exists depends only on the greatest common divisor. In the "mod m" world, a number a has a multiplicative inverse if and only if gcd(m, a) = 1, that is, when the two numbers are relatively prime.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup> When m is prime, every nonzero integer not a multiple of m has an inverse; when m is composite, some nonzero elements lack one. Modulo 4, for instance, 1 and 3 are their own inverses, but 2 has none.<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup>

The inverse, when it exists, is unique up to adding multiples of m, so it is customary to report the representative between 0 and m − 1. GMP's `mpz_invert` is specified to return a result satisfying 0 ≤ rop < |op2|, with 0 possible only in the degenerate case |op2| = 1.<sup>[6](https://gmplib.org/gmp-man-6.3.0.pdf)</sup>

## Computing the inverse with the extended Euclidean algorithm

The extended [Euclidean algorithm](https://www.edgepedia.org/euclidean-algorithm) computes not just the gcd of its arguments but two cofactors: it returns integers g, s, and t such that g = gcd(a, b) and a·s + b·t = g. This is [Bézout's identity](https://www.edgepedia.org/bezouts-identity), and it converts the existence statement into a construction.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup>

Suppose the modulus is m and gcd(m, a) = 1. Running the algorithm on (m, a) returns (1, s, t) with 1 = s·m + t·a. Reducing both sides modulo m gives t·a ≡ 1 (mod m), so the coefficient t returned by the algorithm is exactly the inverse of a mod m. The cost is Θ(log a) steps, the same as the ordinary Euclidean algorithm.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup> A recursive formulation keeps track of the coefficients as the recursion unwinds: with base case returning (m, 1, 0) when the second argument is 0, and the step returning (d, y, x − ⌊m/n⌋·y) from the recursive call on (n, m mod n).<sup>[7](https://people.eecs.berkeley.edu/~demmel/cs70_Spr11/Lectures/CS70_Lecture10_Feb09.html)</sup>

The naive alternative, testing every candidate x until a·x mod m equals 1, works but scales with m rather than with log m, which is impractical for the large numbers used in cryptography.<sup>[3](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup>

## Computing the inverse by exponentiation

[Euler's theorem](https://www.edgepedia.org/eulers-theorem) states that when b and m are relatively prime, b^(φ(m)) ≡ 1 (mod m), where φ is [Euler's totient function](https://www.edgepedia.org/eulers-totient-function). Raising both sides appropriately gives b⁻¹ = b^(φ(m)−1) (mod m).<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup> When the modulus p is prime, φ(p) = p − 1, so the inverse of any nonzero element is b^(p−2); this is a consequence of [Fermat's little theorem](https://www.edgepedia.org/fermats-little-theorem).<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup>

This exponentiation method is simple and naturally constant-time, since the exponent depends only on the modulus, but it costs a full modular exponentiation. A 2019 analysis by Daniel J. Bernstein, a mathematician and cryptographer at the University of Illinois at Chicago, and Bo-Yin Yang of Academia Sinica compares the costs: computing 1/x in a prime field as x^(p−2) takes n^(3+o(1)) bit operations with schoolbook multiplication, while extensions of Euclid's algorithm take n^(2+o(1)), a full exponent-exponent gap in favor of the Euclidean approach.<sup>[8](https://ches.iacr.org/2019/src/slides/Day1/Session4_EfficientImp_onlypdfs/Paper2_20190826-2.pdf)</sup>

## Role in cryptography

Modular inversion is a core step in public-key systems. In RSA key generation, the private exponent d is defined as the multiplicative inverse of the public exponent e modulo φ(n), the totient of the modulus n; the pair e·d ≡ 1 (mod φ(n)) is what makes decryption undo encryption.<sup>[4](https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture12.pdf)</sup> The same inversion appears in digital signatures: NIST's FIPS 186-5, the Digital Signature Standard finalized in February 2023, requires computing the inverse of the per-message secret k modulo n for ECDSA signature generation and the inverse of the signature component s for verification, and provides a reference extended-Euclidean-style routine in its Appendix B.1 while permitting other constant-time algorithms that produce an equivalent result.<sup>[9](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup>

**Side-channel constraints.** In elliptic curve cryptography, inversion is more complex to implement than addition or multiplication, and variable-time Euclidean algorithms leak information about secret values through execution timing. Constant-time modular inversion (CTMI) algorithms address this. The Bernstein–Yang divstep algorithm has been adopted as the de facto standard for CTMI, and the NTRU post-quantum scheme's inverse algorithm, submitted to the third round of NIST's post-quantum standardization, is a constant-time algorithm based on it, running a fixed 2N + 1 iterations to invert a polynomial of degree N.<sup>[10](https://ken.ieice.org/ken/paper/202603030cTZ/eng/)</sup><sup> • </sup><sup>[11](https://link.springer.com/article/10.1007/s13389-025-00380-w)</sup> Bernstein and Yang's own algorithm achieves n^(1+o(1)) bit operations while running in constant time, without a division subroutine between recursive calls.<sup>[8](https://ches.iacr.org/2019/src/slides/Day1/Session4_EfficientImp_onlypdfs/Paper2_20190826-2.pdf)</sup>

## In software

General-purpose arithmetic libraries expose inversion directly. GMP's `mpz_invert(rop, op1, op2)` computes the inverse of op1 modulo op2, returning a nonzero value on success and 0 when no inverse exists; internally it calls the extended GCD routine but saves time by not computing both Bézout coefficients.<sup>[6](https://gmplib.org/gmp-man-6.3.0.pdf)</sup><sup> • </sup><sup>[12](https://gmplib.org/list-archives/gmp-discuss/2002-November/000057.html)</sup> Python built the operation into its three-argument `pow` in version 3.8, which allows a negative exponent when the base is relatively prime to the modulus: `pow(38, -1, mod=97)` returns 23, and indeed 23 · 38 mod 97 equals 1.<sup>[5](https://docs.python.org/3/library/functions.html)</sup> The Wolfram Language offers `ModularInverse[b, m]` and `PowerMod[b, -1, m]`.<sup>[1](https://mathworld.wolfram.com/ModularInverse.html)</sup>

## References

1. [Weisstein, Eric W. "Modular Inverse." MathWorld – A Wolfram Resource.](https://mathworld.wolfram.com/ModularInverse.html)
2. [Gauss: "Disquisitiones Arithmeticae", MacTutor History of Mathematics, University of St Andrews.](https://mathshistory.st-andrews.ac.uk/Extras/Gauss_Disquisitiones/)
3. [Brown, W. C. SI335 Unit 3: Number-Theoretic Computations, United States Naval Academy.](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)
4. [Kak, A. Lecture 12: Public-Key Cryptography and the RSA, Purdue University.](https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture12.pdf)
5. [Built-in Functions, Python 3 documentation.](https://docs.python.org/3/library/functions.html)
6. [GNU MP 6.3.0 Manual, Chapter 5: Integer Functions.](https://gmplib.org/gmp-man-6.3.0.pdf)
7. [Demmel, J. CS 70 Lecture 10: Modular Arithmetic, UC Berkeley.](https://people.eecs.berkeley.edu/~demmel/cs70_Spr11/Lectures/CS70_Lecture10_Feb09.html)
8. [Bernstein, D. J. and Yang, B.-Y. Fast Constant-Time GCD Computation and Modular Inversion, CHES 2019.](https://ches.iacr.org/2019/src/slides/Day1/Session4_EfficientImp_onlypdfs/Paper2_20190826-2.pdf)
9. [FIPS 186-5: Digital Signature Standard, NIST, February 2023.](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)
10. [Ozaki, T. and Miyaji, A. Revisited Constant-Time Modular Inversion, IEICE Tech. Rep. ICSS2025-110.](https://ken.ieice.org/ken/paper/202603030cTZ/eng/)
11. [Fast polynomial inversion algorithms for the post-quantum cryptography, Journal of Cryptographic Engineering (2025).](https://link.springer.com/article/10.1007/s13389-025-00380-w)
12. [Granlund, T. mpz_invert function, GMP discussion list, November 2002.](https://gmplib.org/list-archives/gmp-discuss/2002-November/000057.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Congruences and modular arithmetic*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license