Inverse Modulo Calculator

Compute modular multiplicative inverse x with a·x ≡ 1 (mod m)

Compute modular inverse

Modular multiplicative inverse

Find x such that a·x ≡ 1 (mod m). A solution exists iff gcd(a, m) = 1. Computation uses the extended Euclidean algorithm.

7 · x ≡ 1 (mod 5)
Enter parameters
Integer a ≥ 1
Integer m ≥ 2
Calculation result
x =
Calculation: Find x such that a·x ≡ 1 (mod m)

Modular Inverse Info

Existence condition

The inverse exists only if: gcd(a,m) = 1

gcd(a,m)=1 coprime x⁻¹

Definition: x is the modular inverse of a modulo m if a·x ≡ 1 (mod m)
Computation: Extended Euclidean algorithm

Small examples
3⁻¹ mod 7: 3·5 ≡ 1 (mod 7) → x = 5
2⁻¹ mod 5: 2·3 ≡ 1 (mod 5) → x = 3
6⁻¹ mod 9: gcd(6,9)=3 → no inverse


Formulas and definitions

Definition
\[a \cdot x \equiv 1 \pmod{m}\]

x is the modular inverse of a modulo m

Existence condition
\[\gcd(a, m) = 1\]

a and m must be coprime

Extended Euclid
\[as + mt = \gcd(a, m) = 1\] \[\Rightarrow s \equiv a^{-1} \pmod{m}\]

Computed via the extended Euclidean algorithm

Fermat (m prime)
\[a^{m-1} \equiv 1 \pmod{m}\] \[\Rightarrow a^{-1} \equiv a^{m-2} \pmod{m}\]

For prime m via Fermat's little theorem

Example: inverse of 3 modulo 7

Step-by-step using extended Euclid
Step 1: Euclidean algorithm
7 = 2 · 3 + 1
3 = 3 · 1 + 0

gcd(3,7) = 1 ✓ (inverse exists)

Step 2: Back-substitution
1 = 7 - 2 · 3
1 = 7 · 1 + 3 · (-2)

Thus: s = -2, t = 1

3⁻¹ ≡ -2 ≡ 5 (mod 7)
Verification
\[3 \cdot 5 = 15\] \[15 = 2 \cdot 7 + 1\] \[15 \equiv 1 \pmod{7} \checkmark\]
Check all candidates
3·1 = 3 ≢ 1 (mod 7)
3·2 = 6 ≢ 1 (mod 7)
3·3 = 9 ≡ 2 (mod 7)
3·4 = 12 ≡ 5 (mod 7)
3·5 = 15 ≡ 1 (mod 7) ✓
3·6 = 18 ≡ 4 (mod 7)
Algorithm steps
1. compute gcd
2. back-substitute
3. find coefficients s
4. make positive

Systematic computation via the extended Euclidean algorithm

Applications of modular inverses

Modular inverses are central in number theory and cryptography:

Cryptography
  • RSA encryption (d ≡ e⁻¹ mod φ(n))
  • Elliptic curve cryptography
  • Digital signatures
  • Diffie-Hellman key exchange
Number theory
  • Chinese remainder theorem
  • Solve linear congruences
  • Modular fraction arithmetic
  • Primality tests
Computer Science
  • Hash functions
  • Error-correcting codes
  • Pseudo-random generators
  • Modular exponentiation
Mathematics
  • Group theory (unit group)
  • Algebraic structures
  • Diophantine equations
  • Abstract algebra

Modular inverses: Basis of modern cryptography

Modular inverses form a fundamental concept in elementary number theory with enormous practical importance. The multiplicative inverse of a modulo m is the number x for which a·x ≡ 1 (mod m). This simple definition leads to deep mathematical structures and enables modern cryptographic schemes such as RSA. The extended Euclidean algorithm provides an efficient constructive method.

Properties
  • Exists only if gcd(a,m) = 1
  • Unique modulo m
  • Structure of the unit group
  • Extension of fraction concept
Significance
  • Basis for RSA cryptography
  • Solve linear congruences
  • Modular arithmetic
  • Algebraic number theory
Computation
  • Extended Euclidean algorithm
  • Fermat's little theorem (for primes)
  • Euler's theorem (general)
  • Fast modular exponentiation
Summary

Modular inverses connect elementary number theory with modern cryptography. The existence condition gcd(a,m) = 1 defines the unit group modulo m and enables secure encryption schemes. The extended Euclidean algorithm not only proves existence constructively but also provides an efficient computation method. From ancient number theory to digital security, modular inverses demonstrate the timeless relevance of mathematical foundations.