ToolSphere
Back to all articles
student

Modular Inverse: Extended Euclid Step by Step

2026-11-1111 min read

Try it: free Modular Arithmetic Calculator

Compute modular inverses, powers, and gcd step by step

Open →

In modular arithmetic, standard division does not exist. You cannot simply divide 7 by 3 when working modulo 11. Instead, division is defined by multiplying by the modular multiplicative inverse. Finding this inverse is a core topic in discrete mathematics, abstract algebra, and computer science courses (such as UC Berkeley CS 70, MIT 6.042J, Stanford CS 103, and CMU 15-251). It forms the theoretical backbone of modern public-key cryptography, including RSA and Diffie-Hellman key exchange.

The standard tool for computing modular inverses by hand and in software is the Extended Euclidean Algorithm. When combined with modular exponentiation by repeated squaring, it gives computer scientists the ability to solve modular congruences and compute powers on thousands of bits in milliseconds.

This guide walks through both algorithms step by step. Every equation, table row, and intermediate value in the examples below is verified directly by running ToolSphere's discrete mathematics library.


What Is a Modular Inverse?

Let a and n be integers with n > 1. The modular multiplicative inverse of a modulo n is an integer x such that:

a · x ≡ 1 (mod n)

In ordinary arithmetic, the multiplicative inverse of a number a is its reciprocal 1/a, because a · (1/a) = 1. In modular arithmetic, all values are constrained to integers in the range 0 through n − 1. The modular inverse x (often written a^(−1) mod n) is the unique integer in {0, 1, ..., n − 1} that multiplies with a to leave a remainder of 1 when divided by n.

Why Modular Division Requires the Inverse

Suppose you need to solve the congruence equation:

b · x ≡ c (mod n)

In elementary algebra, you would divide both sides by b. In modular arithmetic, you multiply both sides by b^(−1):

b^(−1) · b · x ≡ b^(−1) · c (mod n)

1 · x ≡ b^(−1) · c (mod n)

x ≡ (c · b^(−1)) mod n

If b^(−1) does not exist, the division c / b (mod n) is undefined.


The Coprimality Condition: When Does an Inverse Exist?

A modular inverse a^(−1) mod n exists if and only if a and n are coprime (relatively prime), meaning their greatest common divisor is 1:

gcd(a, n) = 1

Why Non-Coprime Integers Have No Inverse

If gcd(a, n) = d > 1, then d divides both a and n. Any multiple a · x must also be divisible by d, and any term n · y is divisible by d. Therefore:

a · x − n · y

is a multiple of d. But for a · x ≡ 1 (mod n) to hold, there must exist integers x and y such that a · x − n · y = 1. Because d > 1, the value 1 is not divisible by d. Hence, no integer solution can ever exist.

Counterexample: Compute 15^(−1) mod 35.

  • Running the Euclidean algorithm yields gcd(15, 35) = 5.
  • Because 5 ≠ 1, 15 and 35 are not coprime.
  • Any multiple of 15 modulo 35 can only produce remainders that are multiples of 5: {0, 5, 10, 15, 20, 25, 30}. It is impossible to produce a remainder of 1. Therefore, 15^(−1) mod 35 does not exist.

You can verify whether any pair is coprime instantly with the modular arithmetic calculator.


The Extended Euclidean Algorithm

The standard Euclidean algorithm computes gcd(a, n) through repeated integer division. The Extended Euclidean Algorithm goes one step further: it also finds integers x and y that satisfy Bezout's Identity:

a · x + n · y = gcd(a, n)

When gcd(a, n) = 1, Bezout's identity becomes:

a · x + n · y = 1

Taking both sides modulo n:

a · x + 0 ≡ 1 (mod n)

a · x ≡ 1 (mod n)

The Bezout coefficient x is the modular inverse of a modulo n! If x turns out to be negative, we add n to obtain the canonical positive inverse in the range [0, n − 1]:

x_canonical = (x mod n + n) mod n


The Tabular Method: Step-by-Step Recurrence

College exams typically require setting up an Extended Euclidean table. The tabular method computes quotients and updates three parallel sequences: remainders r_i, coefficients of a (x_i), and coefficients of n (y_i).

Every row i maintains the invariant:

r_i = x_i · a + y_i · n

Recurrence Relations

For each step i ≥ 2:

  1. Quotient: q_i = ⌊r_{i−2} / r_{i−1}⌋ (integer division)
  2. Remainder: r_i = r_{i−2} − q_i · r_{i−1}
  3. Coefficient x: x_i = x_{i−2} − q_i · x_{i−1}
  4. Coefficient y: y_i = y_{i−2} − q_i · y_{i−1}

Initial Conditions

The table starts with two initialization rows (rows 0 and 1):

  • Row 0: r_0 = n, x_0 = 0, y_0 = 1, because n = (0) · a + (1) · n.
  • Row 1: r_1 = a, x_1 = 1, y_1 = 0, because a = (1) · a + (0) · n.

The algorithm terminates when remainder r_k = 0. The previous row k − 1 contains the greatest common divisor in r_{k−1} and the Bezout coefficients in x_{k−1} and y_{k−1}.


Worked Example 1: Finding 17^(−1) mod 43

Let us find the modular inverse of a = 17 modulo n = 43.

Step 0: Setup Initial Rows

  • Row 0: r_0 = 43, x_0 = 0, y_0 = 1.
  • Row 1: r_1 = 17, x_1 = 1, y_1 = 0.

Step 1: Divide 43 by 17 (Row 2)

  • Quotient: q_2 = ⌊43 / 17⌋ = 2
  • Remainder: r_2 = 43 − 2 · 17 = 9
  • x_2 = x_0 − q_2 · x_1 = 0 − 2 · 1 = −2
  • y_2 = y_0 − q_2 · y_1 = 1 − 2 · 0 = 1
  • Invariant check: (−2) · 17 + (1) · 43 = −34 + 43 = 9.

Step 2: Divide 17 by 9 (Row 3)

  • Quotient: q_3 = ⌊17 / 9⌋ = 1
  • Remainder: r_3 = 17 − 1 · 9 = 8
  • x_3 = x_1 − q_3 · x_2 = 1 − 1 · (−2) = 3
  • y_3 = y_1 − q_3 · y_2 = 0 − 1 · 1 = −1
  • Invariant check: (3) · 17 + (−1) · 43 = 51 − 43 = 8.

Step 3: Divide 9 by 8 (Row 4)

  • Quotient: q_4 = ⌊9 / 8⌋ = 1
  • Remainder: r_4 = 9 − 1 · 8 = 1
  • x_4 = x_2 − q_4 · x_3 = −2 − 1 · 3 = −5
  • y_4 = y_2 − q_4 · y_3 = 1 − 1 · (−1) = 2
  • Invariant check: (−5) · 17 + (2) · 43 = −85 + 86 = 1.

Step 4: Divide 8 by 1 (Row 5)

  • Quotient: q_5 = ⌊8 / 1⌋ = 8
  • Remainder: r_5 = 8 − 8 · 1 = 0
  • x_5 = x_3 − q_5 · x_4 = 3 − 8 · (−5) = 3 + 40 = 43
  • y_5 = y_3 − q_5 · y_4 = −1 − 8 · 2 = −17

Full Step Table for 17 mod 43

Step Quotient (q_i) Remainder (r_i) x_i (coeff of 17) y_i (coeff of 43) Equation: r_i = x_i · 17 + y_i · 43
0 − 43 0 1 43 = (0) × 17 + (1) × 43
1 − 17 1 0 17 = (1) × 17 + (0) × 43
2 2 9 −2 1 9 = (−2) × 17 + (1) × 43
3 1 8 3 −1 8 = (3) × 17 + (−1) × 43
4 1 1 −5 2 1 = (−5) × 17 + (2) × 43
5 8 0 43 −17 0 = (43) × 17 + (−17) × 43

Extracting and Normalizing the Answer

Row 4 gives gcd(17, 43) = 1 and Bezout identity:

(−5) · 17 + (2) · 43 = 1

Taking modulo 43:

(−5) · 17 ≡ 1 (mod 43)

Because the coefficient −5 is negative, normalize to the canonical positive integer in [0, 42]:

x = −5 + 43 = 38

Verification:
17 × 38 = 646
646 ÷ 43 = 15 remainder 1 (15 × 43 = 645).
Since 646 = 15 × 43 + 1 ≡ 1 (mod 43), 38 is the exact modular inverse.


Worked Example 2: Finding 17^(−1) mod 60

Now let us examine a composite modulus: a = 17 and n = 60. Modulus 60 is common in clock arithmetic and discrete math homework.

Setup and Step Calculations

  • Row 0: r_0 = 60, x_0 = 0, y_0 = 1.
  • Row 1: r_1 = 17, x_1 = 1, y_1 = 0.
  • Row 2: q_2 = ⌊60 / 17⌋ = 3.
    • r_2 = 60 − 3 · 17 = 9
    • x_2 = 0 − 3 · 1 = −3
    • y_2 = 1 − 3 · 0 = 1
    • Equation: 9 = (−3) · 17 + (1) · 60
  • Row 3: q_3 = ⌊17 / 9⌋ = 1.
    • r_3 = 17 − 1 · 9 = 8
    • x_3 = 1 − 1 · (−3) = 4
    • y_3 = 0 − 1 · 1 = −1
    • Equation: 8 = (4) · 17 + (−1) · 60
  • Row 4: q_4 = ⌊9 / 8⌋ = 1.
    • r_4 = 9 − 1 · 8 = 1
    • x_4 = −3 − 1 · 4 = −7
    • y_4 = 1 − 1 · (−1) = 2
    • Equation: 1 = (−7) · 17 + (2) · 60
  • Row 5: q_5 = ⌊8 / 1⌋ = 8.
    • r_5 = 8 − 8 · 1 = 0
    • x_5 = 4 − 8 · (−7) = 60
    • y_5 = −1 − 8 · 2 = −17

Full Step Table for 17 mod 60

Step Quotient (q_i) Remainder (r_i) x_i (coeff of 17) y_i (coeff of 60) Equation: r_i = x_i · 17 + y_i · 60
0 − 60 0 1 60 = (0) × 17 + (1) × 60
1 − 17 1 0 17 = (1) × 17 + (0) × 60
2 3 9 −3 1 9 = (−3) × 17 + (1) × 60
3 1 8 4 −1 8 = (4) × 17 + (−1) × 60
4 1 1 −7 2 1 = (−7) × 17 + (2) × 60
5 8 0 60 −17 0 = (60) × 17 + (−17) × 60

Extracting and Normalizing the Answer

From row 4, gcd(17, 60) = 1 and Bezout identity is:

(−7) · 17 + (2) · 60 = 1

Modulo 60 reduction:

(−7) · 17 ≡ 1 (mod 60)

Normalize the negative coefficient to [0, 59]:

x = −7 + 60 = 53

Verification:
17 × 53 = 901
901 ÷ 60 = 15 remainder 1 (15 × 60 = 900).
Since 901 = 15 × 60 + 1 ≡ 1 (mod 60), 53 is the exact modular inverse.


Modular Exponentiation: Repeated Squaring

Once you know how to divide with modular inverses, the next fundamental operation is raising a number to a large power modulo n:

result = a^b mod n

If b is 1,000,000, computing a^b directly is impossible on a standard computer because the number would require hundreds of thousands of digits before taking the modulus. Even a simple for-loop performing b multiplications would take far too long for cryptographic exponents with hundreds of bits.

The solution is modular exponentiation by repeated squaring (also known as binary exponentiation). It computes a^b mod n using at most 2 · ⌊log_2 b⌋ modular multiplications, reducing time complexity from O(b) to O(log b).

How Repeated Squaring Works

  1. Binary Decomposition: Express the exponent b in binary:
    b = ∑ b_i · 2^i, where b_i ∈ {0, 1}.
  2. Successive Squaring: Compute powers of two exponents:
    • a^(2^0) mod n = a mod n
    • a^(2^1) mod n = (a^(2^0))^2 mod n
    • a^(2^2) mod n = (a^(2^1))^2 mod n
    • In general, each term is the square of the previous term modulo n.
  3. Accumulate: Start with an accumulator result = 1. Scan the binary bits of b from right to left (index i = 0, 1, 2, ...):
    • If bit b_i = 1, multiply result = (result · a^(2^i)) mod n.
    • If bit b_i = 0, skip the multiplication (leave result unchanged).

Worked Example 1: Compute 3^13 mod 7

Let a = 3, b = 13, and n = 7.

Binary Decomposition of Exponent 13

13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0
In binary: 13 = 1101_2 (4 bits: bits 0, 1, 2, 3).

Step-by-Step Repeated Squaring Table

Step Bit Index (i) Power of Two (2^i) Bit Value (b_i) Squared Power (3^(2^i) mod 7) Action Intermediate Result
1 0 1 1 3^1 mod 7 = 3 Bit is 1: multiply accumulator by 3 mod 7 1 × 3 mod 7 = 3
2 1 2 0 3^2 mod 7 = 9 mod 7 = 2 Bit is 0: skip multiplication Accumulator stays 3
3 2 4 1 2^2 mod 7 = 4 mod 7 = 4 Bit is 1: multiply accumulator by 4 mod 7 3 × 4 mod 7 = 12 mod 7 = 5
4 3 8 1 4^2 mod 7 = 16 mod 7 = 2 Bit is 1: multiply accumulator by 2 mod 7 5 × 2 mod 7 = 10 mod 7 = 3

Final Result: 3^13 mod 7 = 3.

Operation Count: 3 squarings and 3 multiplications. Without repeated squaring, computing 3^13 would require 12 multiplications.


Worked Example 2: Compute 17^43 mod 60

Now let us compute a larger power using the values from our earlier example: 17^43 mod 60.

Binary Decomposition of Exponent 43

43 = 32 + 8 + 2 + 1 = 2^5 + 2^3 + 2^1 + 2^0
In binary: 43 = 101011_2 (6 bits).

Step-by-Step Repeated Squaring Table

Step Bit Index (i) Power of Two (2^i) Bit Value (b_i) Squared Power (17^(2^i) mod 60) Action Intermediate Result
1 0 1 1 17^1 mod 60 = 17 Bit is 1: multiply accumulator by 17 mod 60 1 × 17 mod 60 = 17
2 1 2 1 17^2 mod 60 = 289 mod 60 = 49 Bit is 1: multiply accumulator by 49 mod 60 17 × 49 mod 60 = 833 mod 60 = 53
3 2 4 0 49^2 mod 60 = 2401 mod 60 = 1 Bit is 0: skip multiplication Accumulator stays 53
4 3 8 1 1^2 mod 60 = 1 Bit is 1: multiply accumulator by 1 mod 60 53 × 1 mod 60 = 53
5 4 16 0 1^2 mod 60 = 1 Bit is 0: skip multiplication Accumulator stays 53
6 5 32 1 1^2 mod 60 = 1 Bit is 1: multiply accumulator by 1 mod 60 53 × 1 mod 60 = 53

Final Result: 17^43 mod 60 = 53.

Notice that once the squared power reached 1 at step 3 (17^4 mod 60 = 1), every subsequent squaring yielded 1^2 = 1. This illustrates Euler's Totient Theorem: for coprime integers a and n, a^φ(n) ≡ 1 (mod n). For n = 60, φ(60) = 60 · (1 − 1/2) · (1 − 1/3) · (1 − 1/5) = 16. In fact, the Carmichael function gives λ(60) = lcm(2, 2, 4) = 4, proving that 17^4 ≡ 1 (mod 60).


Negative Exponents: Combining Powers and Inverses

What does it mean to evaluate a negative modular exponent, such as a^(−b) mod n?

By algebraic rules of exponents:

a^(−b) ≡ (a^(−1))^b (mod n)

To evaluate 17^(−43) mod 60:

  1. Find the modular inverse 17^(−1) mod 60 = 53 using the Extended Euclidean Algorithm.
  2. Evaluate 53^43 mod 60 using repeated squaring.

Because 17 · 53 ≡ 1 (mod 60), computing powers of the inverse yields the exact mathematically consistent negative modular power. If gcd(a, n) ≠ 1, the negative power is undefined because no inverse exists.


Application in RSA Cryptography

The combination of the Extended Euclidean Algorithm and repeated squaring is the foundational engine of RSA encryption:

  1. Key Generation:
    • Choose two distinct large prime numbers p and q.
    • Compute modulus N = p · q and totient φ(N) = (p − 1)(q − 1).
    • Choose a public exponent e coprime to φ(N) (commonly e = 65537 = 2^16 + 1).
    • Use the Extended Euclidean Algorithm to compute the private key exponent d:
      d = e^(−1) mod φ(N)
      meaning e · d ≡ 1 (mod φ(N)).
  2. Encryption:
    • Encrypt plaintext message m into ciphertext c:
      c = m^e mod N (computed via repeated squaring).
  3. Decryption:
    • Decrypt ciphertext c back into plaintext message m:
      m = c^d mod N (computed via repeated squaring).

Without the Extended Euclidean Algorithm, computing d from e and φ(N) would be impossible. Without repeated squaring, computing m^e mod N on 2048-bit numbers would take astronomical time. Together, they execute in fractions of a millisecond.


Common Homework and Exam Pitfalls

  1. Forgetting to Check Coprimality First: Always verify that gcd(a, n) = 1. If gcd(a, n) > 1, do not continue the table expecting an inverse; immediately state that no inverse exists.
  2. Leaving the Final Answer Negative: If the Bezout coefficient x is negative (such as x = −5 in 17 mod 43), students frequently write −5 as the final exam answer. Most instructors require the canonical positive residue [0, n − 1]. Always add the modulus: −5 + 43 = 38.
  3. Swapping Rows 0 and 1: Row 0 must be initialized with the modulus n (x = 0, y = 1), and Row 1 must be initialized with the operand a (x = 1, y = 0). Swapping them swaps the Bezout coefficients.
  4. Sign Errors in Recurrence Updates: Remember that x_i = x_{i−2} − q_i · x_{i−1} contains a subtraction. When x_{i−1} is already negative, subtracting it results in addition: 1 − 1 · (−2) = 1 + 2 = 3.
  5. Floating-Point Rounding in Repeated Squaring: When implementing repeated squaring in code, never use Math.pow(a, b) % n. Floating-point numbers lose precision above 53 bits (approximately 9 × 10^15). Apply the modulo operator mod n after every single multiplication and squaring.

Frequently Asked Questions

What is the difference between Euclidean and Extended Euclidean algorithms?

The standard Euclidean algorithm only finds the greatest common divisor gcd(a, b) by tracking remainders. The Extended Euclidean algorithm tracks both the quotients and the Bezout coefficients x and y, expressing gcd(a, b) as a linear combination a · x + b · y.

Can a negative number have a modular inverse?

Yes. First reduce the negative number modulo n to its canonical positive form a_pos = (a mod n + n) mod n. For example, to find (−3)^(−1) mod 7, notice −3 ≡ 4 (mod 7). The inverse of 4 modulo 7 is 2 (since 4 × 2 = 8 ≡ 1 mod 7), so (−3)^(−1) mod 7 = 2.

Why do we add the modulus when the Bezout coefficient is negative?

Modular congruence states that x and x + k · n are congruent modulo n for any integer k. Adding n changes the representative without changing its residue. Adding n shifts a negative value into the standard canonical range [0, n − 1].

How does Fermat's Little Theorem relate to the modular inverse?

When the modulus p is a prime number and gcd(a, p) = 1, Fermat's Little Theorem states a^(p−1) ≡ 1 (mod p). Rewriting this as a · a^(p−2) ≡ 1 (mod p) reveals that a^(p−2) mod p is the modular inverse of a. However, when n is composite, Fermat's Little Theorem does not apply, making the Extended Euclidean Algorithm the universal choice.

Why is repeated squaring faster than multiplying in a loop?

A loop multiplying a by itself b times requires b − 1 operations, giving O(b) linear time complexity. Repeated squaring processes the binary representation of b, requiring at most 2 · ⌊log_2 b⌋ multiplications. For an exponent like b = 1,000,000, linear multiplication takes 1,000,000 steps, while repeated squaring takes fewer than 40 steps.

What happens if gcd(a, n) is greater than 1?

If gcd(a, n) > 1, a and n share a common divisor d > 1. In abstract algebra terms, a is a zero-divisor in the ring of integers modulo n, and no modular inverse exists.

Can repeated squaring evaluate negative exponents?

Yes, provided that gcd(a, n) = 1. First compute the modular inverse x = a^(−1) mod n using the Extended Euclidean Algorithm, then evaluate x^|b| mod n with repeated squaring.

What is the computational complexity of the Extended Euclidean Algorithm?

By Lamé's Theorem, the Euclidean algorithm requires at most 5 · log_10(min(a, n)) division steps. The time complexity is O((log n)^2) bit operations using standard multiplication and division algorithms, making it exceptionally fast even for 4096-bit cryptographic keys.


Interactive Verification

Practice your own discrete math homework problems, generate full step-by-step Bezout tables, and trace binary exponentiation trees on the modular arithmetic calculator. For related discrete mathematics and hardware topics, explore the logic gates and truth tables guide and the cache mapping guide.

Use the RSA & ECDSA Key Generator to explore RSA keys alongside your modular arithmetic study.

Looking for other tools?

Explore ToolSphere Homepage →