Modular inverse: the element that "divides" mod m

The modular inverse of a with respect to modulus m is the integer x such that a · x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1, i.e. a and m are coprime. When it exists, it is unique in {0, 1, ..., m−1} and is denoted a⁻¹ mod m. Examples: 3⁻¹ mod 7 = 5 (since 3·5 = 15 = 2·7 + 1); 10⁻¹ mod 17 = 12. 2⁻¹ mod 4 does not exist because gcd(2,4) = 2. The modular inverse is the foundation of arithmetic in ℤ/mℤ, used in cryptography (RSA, ElGamal, Diffie-Hellman), coding theory and numerical algorithms.

Extended Euclidean algorithm

The most efficient way to compute a⁻¹ mod m is the extended Euclidean algorithm, which finds Bezout coefficients x, y such that a·x + m·y = gcd(a, m). If gcd(a,m)=1, then a·x ≡ 1 (mod m), so x mod m is the sought inverse. Complexity O(log min(a,m)), much faster than brute force O(m). Example a=3, m=7: 7 = 2·3 + 1 → 1 = 7 − 2·3 → x = −2 ≡ 5 (mod 7). Hence 3⁻¹ ≡ 5 (mod 7).

Modular exponentiation a^b mod m

Computing a^b when b is large is impractical with direct multiplications (result may have billions of digits). Binary exponentiation (square-and-multiply) reduces cost to O(log₂ b) modular multiplications: write b in binary, scan bit by bit, square a at each step, multiply by a if bit is 1, reduce mod m every time. Example 7²¹ mod 100: 21 = 10101₂, result 07. Fundamental in RSA (a^d mod n for decryption) and primality tests (Miller-Rabin, Fermat).

Fermat's little theorem and Euler's theorem

If p is prime and gcd(a,p)=1, then a^(p−1) ≡ 1 (mod p) (Fermat). Hence a⁻¹ ≡ a^(p−2) mod p. Euler generalizes: for any m, a^φ(m) ≡ 1 (mod m) if gcd(a,m)=1, where φ is Euler's totient (count of integers in [1,m] coprime with m). For m = p·q product of two distinct primes (RSA), φ(m) = (p−1)(q−1). Chinese Remainder Theorem lets you decompose mod m computations into mod p and mod q computations, which are faster.

Linear congruences a·x ≡ b (mod m)

A congruence a·x ≡ b (mod m) has solutions iff d = gcd(a, m) divides b. Then there are exactly d distinct solutions modulo m. Procedure: divide the congruence by d to get a'·x ≡ b' (mod m'), where a'=a/d, b'=b/d, m'=m/d; unique solution is x₀ = a'⁻¹ · b' (mod m'). The d original solutions are x₀, x₀+m', x₀+2m', ..., x₀+(d−1)m' (mod m).

Cryptographic applications

RSA: private key d = e⁻¹ mod φ(n), with n=pq and e public exponent typically 65537. Decryption: m = c^d mod n. Digital signature: s = H(m)^d mod n. ElGamal and DSA use inverse mod q (group order). Elliptic curves (ECDSA, Ed25519): scalar multiplication uses modular exponentiation on finite fields GF(p) and GF(2ⁿ). High-speed cryptographic hashing requires modular multiplications on 32-64 bit words.

Other uses

Hash algorithms on prime moduli (Rabin-Karp string search); error checking (CRC with polynomials in GF(2)); Reed-Solomon codes (operations in GF(2^m)); pseudo-random generators (LCG: Xₙ₊₁ = a·Xₙ + c mod m); graph theory (cycles in Z/nZ); cryptocurrencies (secp256k1 in Bitcoin/Ethereum, pairings in BLS12-381); blockchain (zk-SNARKs on pairing-friendly curves); signal decimation (resampling in DSP).

How to use

Select mode: Inverse (a, m → a⁻¹ mod m), Exponentiation (a, b, m → a^b mod m), Extended Euclidean (a, b → gcd, x, y such that ax+by=gcd), Linear congruence (a, b, m → all solutions of ax≡b mod m). Positive integers; m ≥ 2.

Modular arithmetic, from the clock to RSA

Modular arithmetic, formalised by Carl Friedrich Gauss in his 1801 Disquisitiones Arithmeticae, is the arithmetic of remainders: like the hours on a clock face, numbers "wrap around" after reaching the modulus. The modular inverse is the operation that turns this world into a field when the modulus is prime, allowing "division". On this structure rest RSA cryptography, the Diffie-Hellman key-exchange protocol and the digital signatures that authenticate every bank transaction and every secure HTTPS connection.

The Chinese remainder theorem

A classic application of the modular inverse is solving systems of congruences with the Chinese remainder theorem, known to Chinese mathematicians as early as the 3rd century. It reconstructs a number from its remainders modulo coprime moduli and is used today to speed up RSA computations, to generate pseudorandom numbers and in big-integer arithmetic. The calculator provides the building blocks — inverse, Bézout and linear congruences — on which these results are built.

Updated July 2026