Modular Inverse: Extended Euclid Pattern

Learning Outcome

After this lesson, you should be able to find a modular inverse when gcd(a,m) is 1 and reject cases where it does not exist.

Problem Statement

Given integers a and m, return the modular inverse of a modulo m, or -1 if it does not exist.

Brute Force Approach

Try every x from 1 to m

• 1 and check whether a * x modulo m equals 1. This is linear in m.

Optimized Approach

Use Extended Euclid to solve ax + my = gcd(a,m). If gcd is 1, normalize x into the range 0 to m

Exact Pseudocode

egcd(a, b):
  if b == 0:
    return (a, 1, 0)
  g, x1, y1 = egcd(b, a % b)
  return (g, y1, x1 - (a // b) * y1)

g, x, y = egcd(a, m)
if g is not 1:
  return -1
return (x % m + m) % m
  

Reference Code

class Solution:
    def modInverse(self, a, m):
        def egcd(x, y):
            if y == 0:
                return x, 1, 0
            g, x1, y1 = egcd(y, x % y)
            return g, y1, x1 - (x // y) * y1

        g, x, _ = egcd(a, m)
        if g != 1:
            return -1
        return (x % m + m) % m
  

Sample Dry Run

Complexity

Edge Cases

• If gcd(a,m) is not 1, no modular inverse exists.
• The coefficient x can be negative and must be normalized.
• Fermat inverse needs prime modulus, but Extended Euclid works for any coprime modulus.

Interview Checklist

• Compute gcd and coefficients with Extended Euclid.
• Return -1 when gcd is not 1.
• Normalize x using (x mod m + m) mod m.

FAQs