Using Inverses to Solve Congruence Problems

What Is a Modular Inverse and Why You Need It

A modular inverse is the number that, when multiplied by your original number, gives you 1 modulo m. Sounds simple. It is simple. But most students mess this up because they confuse it with regular reciprocals.

Here's the deal: for a number a, its inverse modulo m is a number x such that:

a · x ≡ 1 (mod m)

This inverse only exists when a and m are coprime. If gcd(a, m) ≠ 1, you're wasting your time looking for an inverse. Accept it and move on.

When Inverses Actually Appear in Congruence Problems

You need inverses when you're trying to isolate a variable in a congruence. Look at this:

5x ≡ 3 (mod 13)

You can't just divide by 5. Modular arithmetic doesn't work that way. Instead, you find the inverse of 5 modulo 13, multiply both sides, and solve.

This comes up constantly in:

• Cryptography (RSA, in particular)
• Linear congruences with multiple solutions
• Chinese Remainder Theorem problems
• Solving Diophantine equations

Finding Inverses: The Extended Euclidean Algorithm

Skip the trial-and-error method unless m is tiny. The extended Euclidean algorithm is faster and works every time.

The goal: find integers x and y such that ax + my = gcd(a, m) = 1

When gcd = 1, that x is your inverse.

Step-by-Step Example

Find the inverse of 17 modulo 43.

Apply the extended Euclidean algorithm:

43 = 17 × 2 + 9
17 = 9 × 1 + 8
9 = 8 × 1 + 1
8 = 1 × 8 + 0

Now back-substitute:

1 = 9 - 8 × 1
1 = 9 - (17 - 9 × 1) × 1
1 = 9 × 2 - 17 × 1
1 = (43 - 17 × 2) × 2 - 17 × 1
1 = 43 × 2 - 17 × 5

So 17 × (-5) ≡ 1 (mod 43)

The inverse is -5 ≡ 38 (mod 43)

Check: 17 × 38 = 646. Divide by 43: 43 × 15 = 645, remainder 1. It works.

Solving Linear Congruences with Inverses

Here's the real-world application. You have:

7x ≡ 4 (mod 26)

Step 1: Check that gcd(7, 26) = 1. It is, so an inverse exists.

Step 2: Find the inverse of 7 modulo 26.

26 = 7 × 3 + 5
7 = 5 × 1 + 2
5 = 2 × 2 + 1
2 = 1 × 2 + 0

Back-substitute:

1 = 5 - 2 × 2
1 = 5 - (7 - 5) × 2
1 = 5 × 3 - 7 × 2
1 = (26 - 7 × 3) × 3 - 7 × 2
1 = 26 × 3 - 7 × 11

The inverse is -11 ≡ 15 (mod 26)

Step 3: Multiply both sides by the inverse:

15 × 7x ≡ 15 × 4 (mod 26)
x ≡ 60 (mod 26)
x ≡ 8 (mod 26)

Done. x = 8 is your solution.

When No Inverse Exists

If gcd(a, m) ≠ 1, stop trying to find an inverse. It doesn't exist.

For example, 6x ≡ 3 (mod 9) has no inverse because gcd(6, 9) = 3.

In this case, check if the right side is divisible by the gcd. If it is, you have solutions. If not, there are none.

Here, 3 is divisible by 3, so solutions exist. Divide everything by the gcd:

2x ≡ 1 (mod 3)

Now gcd(2, 3) = 1, and the inverse of 2 mod 3 is 2. So x ≡ 2 (mod 3).

The full solution is x ≡ 2, 5, 8 (mod 9).

Quick Reference: Inverse Methods Compared

Getting Started: Practice Problems

Work through these to build muscle memory:

Problem 1: Find the inverse of 11 modulo 26.

Answer: 19 (since 11 × 19 = 209 = 1 + 8 × 26)

Problem 2: Solve 9x ≡ 5 (mod 23).

Answer: Inverse of 9 mod 23 is 18. x ≡ 90 ≡ 21 (mod 23).

Problem 3: Solve 14x ≡ 8 (mod 30).

Answer: gcd(14, 30) = 2, and 2 divides 8. Divide by 2: 7x ≡ 4 (mod 15). Inverse of 7 mod 15 is 13. x ≡ 52 ≡ 7 (mod 15). Full solution: x ≡ 7, 22 (mod 30).

The Bottom Line

Modular inverses are just a tool. The extended Euclidean algorithm finds them reliably. Multiply by the inverse to isolate your variable. Check gcd first—if it's not 1, an inverse doesn't exist and you need a different approach.

That's it. Practice the back-substitution until it's automatic, and you'll handle any congruence problem that comes at you.