Inverse Modulo Calculator

The modular inverse of a mod m is the whole number x from 0 to m − 1 with a·x ≡ 1 (mod m). For a = 7 and m = 26, x = 15, since 7 × 15 = 105 = 4 × 26 + 1.

• It plays the part of 1/a in arithmetic mod m, where fractions do not exist.
• It exists only when a and m share no factor: gcd(a, m) = 1.
• 4 has no inverse mod 26: 4x is always even, and every even number leaves an even remainder mod 26, never 1.
• Each a has exactly 1 inverse from 0 to m − 1. Adding m gives the same class: 15, 41, 67, … all work for 7 mod 26.

Other names: modular multiplicative inverse, inverse modulo m, and a⁻¹ mod m.

To find a⁻¹ mod m, run the extended Euclidean algorithm on m and a, write 1 as a·s + m·t, and take s mod m. For 7⁻¹ mod 26:

1. Divide: 26 = 3 × 7 + 5, 7 = 1 × 5 + 2, 5 = 2 × 2 + 1, 2 = 2 × 1 + 0. The gcd is 1, so an inverse exists.
2. Work back: 1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7.
3. Replace 5: 1 = 3 × (26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7.
4. Take it mod 26: −11 × 7 ≡ 1, so x ≡ −11 ≡ 15.

Check: 7 × 15 = 105, and 105 − 4 × 26 = 1.

Type a and m, and the calculator returns a⁻¹ mod m with the full extended Euclidean steps as you type. The steps:

1. Choose Inverse a⁻¹ mod m for an inverse, or Solve ax ≡ b (mod m) for a linear congruence.
2. Type a and m as whole numbers. Negative a and numbers with hundreds of digits work.
3. Read the inverse, the check a·x mod m = 1, the Bézout coefficients and the negative form x − m.
4. Open the modular clock or the Euclid squares, and the worked steps.

When gcd(a, m) is not 1, the calculator names the shared factor instead of an answer.

a⁻¹ mod m is the x in a·x + m·y = 1; it exists exactly when gcd(a, m) = 1.

• Bézout's identity: whole numbers x and y with a·x + m·y = gcd(a, m) always exist; the extended Euclidean algorithm finds them.
• Prime modulus (Fermat): a⁻¹ ≡ a^(p − 2) (mod p). 3⁻¹ mod 11 = 3⁹ mod 11 = 4.
• Any modulus (Euler): a⁻¹ ≡ a^(φ(m) − 1) (mod m), with φ(m) the count of numbers below m coprime to m.
• Products: (ab)⁻¹ ≡ a⁻¹ · b⁻¹ (mod m).
• Self-inverse: 1 and m − 1 are their own inverses, since (m − 1)² = m² − 2m + 1 ≡ 1.

The extended Euclidean table keeps r = a·s + m·t on every row; the row with r = 1 holds the inverse in the s column.

1. Start with 2 rows: r = m (s = 0, t = 1) and r = a (s = 1, t = 0).
2. Divide the last 2 remainders: q = floor(r₁ / r₂).
3. New row = row 2 above − q × row above, for r, s and t alike.
4. Stop at r = 0. The row above it has r = gcd(a, m).

For 7 mod 26 the s column runs 0, 1, −3, 4, −11, and −11 + 26 = 15. The number of rows grows with the number of digits, so a 300-digit RSA modulus needs only a few hundred divisions.

a has an inverse mod m exactly when gcd(a, m) = 1; mod a prime, every a from 1 to p − 1 has one.

• Mod 10, only 1, 3, 7 and 9 have inverses: 1, 7, 3 and 9. 2, 4, 5, 6 and 8 share a factor with 10.
• Mod 7 (prime), all 6 non-zero numbers have inverses: 1, 4, 5, 2, 3, 6.
• The count of numbers with an inverse is Euler's φ(m): φ(10) = 4, φ(26) = 12, φ(7) = 6.

In a multiplication table mod m, a row contains a 1 exactly when that row's number has an inverse. Rows of numbers that share a factor with m never reach 1.

For a prime p, a⁻¹ ≡ a^(p − 2) (mod p); for any m, a⁻¹ ≡ a^(φ(m) − 1) (mod m) when gcd(a, m) = 1.

• Fermat: a^(p − 1) ≡ 1, so a · a^(p − 2) ≡ 1. For 3 mod 11: 3⁹ = 19683 = 1789 × 11 + 4, so 3⁻¹ = 4.
• Euler: a^φ(m) ≡ 1. For 3 mod 10: φ(10) = 4, so 3⁻¹ = 3³ mod 10 = 7.
• Repeated squaring keeps the work small: a^(p − 2) takes about 2 log₂ p multiplications.

The extended Euclidean algorithm is usually faster and works without knowing whether m is prime or what φ(m) is. Euler's method needs φ(m), which needs the factors of m.

To solve a·x ≡ b (mod m), let d = gcd(a, m); if d divides b, divide everything by d and multiply both sides by the inverse of a/d.

• 7x ≡ 3 (mod 26): d = 1 and 7⁻¹ = 15, so x ≡ 15 × 3 = 45 ≡ 19.
• 4x ≡ 6 (mod 10): d = 2 divides 6. Divide: 2x ≡ 3 (mod 5). 2⁻¹ mod 5 = 3, so x ≡ 9 ≡ 4 (mod 5): x = 4 or 9.
• 4x ≡ 5 (mod 10): d = 2 does not divide 5, so there is no solution.

The number of solutions from 0 to m − 1 is d, spaced m/d apart.

Python 3.8+ has pow(a, -1, m), Java has BigInteger.modInverse, and Wolfram Language has ModularInverse[a, m].

• Python: pow(7, -1, 26) returns 15; it raises ValueError when no inverse exists.
• Java: a.modInverse(m) on 2 BigInteger values; 7 and 26 give 15.
• Wolfram Language: ModularInverse[7, 26] or PowerMod[7, -1, 26].
• PARI/GP: lift(Mod(7, 26)^-1).
• JavaScript, C and Excel: no built-in. Write the extended Euclidean loop; in JavaScript use BigInt for large values.

Mod 26, the 12 numbers coprime to 26 have inverses; the table lists each pair. Click a row to load it into the calculator.

The pairs come in twos: 3 and 9, 5 and 21, 7 and 15, 11 and 19, 17 and 23. 1 and 25 are their own inverses. This table drives the affine cipher, which works on the 26 letters.

The reciprocal 1/a is a fraction; the modular inverse a⁻¹ mod m is a whole number that acts like 1/a when you only keep remainders.

Division mod m means multiplying by the inverse: 3 ÷ 7 mod 26 = 3 × 15 mod 26 = 19.

The affine cipher encrypts a letter x as (a·x + b) mod 26 and decrypts with a⁻¹: x = a⁻¹·(y − b) mod 26. The key a must be coprime to 26, or decryption fails.

• With a = 5 and b = 8, A (0) becomes 8 = I, and H (7) becomes 43 mod 26 = 17 = R.
• 5⁻¹ mod 26 = 21, since 5 × 21 = 105 = 4 × 26 + 1.
• Decrypt R: 21 × (17 − 8) = 189, and 189 mod 26 = 7 = H.

Only 12 values of a work: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 and 25. With 26 shifts, that gives 312 keys.

In RSA, the private exponent d is the modular inverse of the public exponent e: d = e⁻¹ mod φ(n).

1. Pick primes p = 61 and q = 53. Then n = 3233 and φ(n) = 60 × 52 = 3120.
2. Pick e = 17, coprime to 3120.
3. d = 17⁻¹ mod 3120 = 2753, since 17 × 2753 = 46801 = 15 × 3120 + 1.
4. Encrypt 65: 65¹⁷ mod 3233 = 2790. Decrypt: 2790²⁷⁵³ mod 3233 = 65.

Real keys use primes of 1024 bits or more. The extended Euclidean algorithm still finds d in a few hundred steps, while finding p and q from n stays out of reach.