Solving Two Variables in Modular Arithmetic
What You're Actually Trying to Solve
When you have two variables in modular arithmetic, you're dealing with a system of congruences. Something like:
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Your goal is finding a single number x that satisfies both conditions simultaneously. That's it. Nothing more complicated than that.
Most tutorials drag this out with unnecessary theory. You don't need a history lesson on modular arithmetic. You need to know how to actually solve the damn thing.
The Setup: Two Variables, Two Congruences
The general form looks like this:
x ≡ a (mod m)
x ≡ b (mod n)
Where m and n are your moduli (the numbers you're taking mod against). The solution exists and is unique (mod lcm(m,n)) if and only if a ≡ b (mod gcd(m,n)).
That condition is non-negotiable. Check it first, every time.
Quick Check Example
Can you solve:
x ≡ 4 (mod 6)
x ≡ 7 (mod 9)
Check: gcd(6,9) = 3. Does 4 ≡ 7 (mod 3)? Yes, both give remainder 1. This system has a solution.
Method 1: The Chinese Remainder Theorem (CRT)
CRT is the heavy-duty tool for this job. It works when your moduli are coprime (gcd = 1). Here's the formula:
x = a·n·Mn + b·m·Mm (mod m·n)
Where M is the modular inverse. Let me show you what this actually looks like in practice.
Step-by-Step CRT Example
Solve: x ≡ 3 (mod 5) and x ≡ 4 (mod 7)
Step 1: Identify your values
m = 5, n = 7, a = 3, b = 4
Step 2: Calculate M values
M₁ = n = 7
M₂ = m = 5
Step 3: Find modular inverses
Find 7-1 (mod 5): 7 ≡ 2, 2·3 = 6 ≡ 1 ✓ → N₁ = 3
Find 5-1 (mod 7): 5·3 = 15 ≡ 1 ✓ → N₂ = 3
Step 4: Plug into formula
x = (3)(7)(3) + (4)(5)(3) = 63 + 60 = 123
Step 5: Take mod m·n
x = 123 mod 35 = 18
Verify: 18 mod 5 = 3 ✓, 18 mod 7 = 4 ✓
Method 2: Brute Force Substitution
Sometimes the cleanest method is just listing possibilities. This works best when moduli are small.
Example
Solve: x ≡ 2 (mod 4) and x ≡ 5 (mod 6)
List values from first congruence: 2, 6, 10, 14, 18, 22...
Check each against second congruence:
2 mod 6 = 2 ✗
6 mod 6 = 0 ✗
10 mod 6 = 4 ✗
14 mod 6 = 2 ✗
18 mod 6 = 0 ✗
22 mod 6 = 4 ✓
Answer: x = 22 (mod lcm(4,6) = 12, so x ≡ 10 mod 12)
This method is slow but foolproof. No inverse calculations, no formula to forget.
Method 3: Using Extended Euclidean Algorithm
When moduli aren't coprime and gcd > 1, you need this method. It finds the solution by working backwards through the gcd.
Example
Solve: x ≡ 4 (mod 6) and x ≡ 10 (mod 15)
Step 1: Check solvability
gcd(6,15) = 3
4 ≡ 10 (mod 3)? Yes → solvable
Step 2: Reduce the system
Rewrite: x = 4 + 6k
Substitute into second: 4 + 6k ≡ 10 (mod 15)
6k ≡ 6 (mod 15)
Divide by gcd(6,15) = 3: 2k ≡ 2 (mod 5)
Step 3: Solve simplified equation
2k ≡ 2 (mod 5)
k ≡ 1 (mod 5) → k = 1 + 5t
Step 4: Back-substitute
x = 4 + 6(1 + 5t) = 10 + 30t
Answer: x ≡ 10 (mod 30)
Verify: 10 mod 6 = 4 ✓, 10 mod 15 = 10 ✓
Comparing the Methods
| Method | Best For | Speed | Difficulty |
|---|---|---|---|
| CRT | Coprime moduli, formula-based problems | Fast once you know it | Medium (inverses) |
| Brute Force | Small moduli, quick checks | Slow | Easy |
| Extended Euclidean | Non-coprime moduli, general case | Medium | Hardest |
Common Mistakes That Will Blow Your Answer
- Forgetting to check gcd condition. Always verify solvability first. No point solving if there's no solution.
- Screwing up modular inverses. When you need N₁ and N₂, double-check: (M·N) mod the other modulus must equal 1.
- Not reducing the answer. Your solution is always modulo lcm(m,n), not m·n. These are different when moduli aren't coprime.
- Dividing incorrectly. When reducing equations, divide both sides AND the modulus by the gcd. Don't just divide one.
Getting Started: Your Action Plan
When you see a two-variable modular system:
- Write down both congruences clearly. Label which is which (m, n, a, b).
- Calculate gcd(m,n). Use the Euclidean algorithm if they're large.
- Check solvability. Does a ≡ b (mod gcd)? If no, stop—there is no solution.
- Choose your method:
- Moduli are coprime → CRT
- Moduli are small → Brute force
- Moduli share a factor → Extended Euclidean
- Calculate the answer.
- Verify. Plug back into both original congruences. Always.
When You Need Two Variables, Not One
What if your system has two unknowns, not one? Like:
x + y ≡ 3 (mod 5)
x - y ≡ 1 (mod 5)
This is a different beast. You solve it like a normal system of equations, just with mod applied at the end. Add the equations to eliminate y, solve for x, then back-substitute. The solution space will be infinite—pick one value or express in terms of a parameter.
That's a separate topic for another day.
The Bottom Line
Solving two variables in modular arithmetic comes down to three methods, one solvability check, and verification. CRT is fastest for coprime moduli. Brute force is slowest but easiest. Extended Euclidean handles the messy cases.
Pick the right tool. Check your work. That's all there is to it.