Congruences as equations

Suppose we want to solve many congruences such as:

2x ≡ 7 (mod 11)
7x ≡ 4 (mod 11)
x^5 ≡ 3 (mod 4)

And we already have a calculator that solves equations about real numbers very well. How do we convert such congruences into equations?

To solve congruences like:

• $2x \equiv 7 \pmod{11}$
• $7x \equiv 4 \pmod{11}$
• $x^5 \equiv 3 \pmod{4}$

using a calculator that works with real numbers, you need to translate modular arithmetic into standard equations. Here's how you can do it:

---

✅ General Strategy: Use the definition of congruence

Recall:

$$ a \equiv b \pmod{n} \quad \text{means} \quad a = b + kn \quad \text{for some integer } k. $$

We can turn a modular congruence into an ordinary equation involving an unknown integer $k$.

---

🔁 Step-by-step conversion

Example 1: $2x \equiv 7 \pmod{11}$

We rewrite this as:

$$ 2x = 7 + 11k \quad \text{for some integer } k. $$

Now solve for $x$ in terms of $k$:

$$ x = \frac{7 + 11k}{2} $$

Now you can try integer values of $k$ and check when $x$ becomes an integer.

For example:

• $k = 1$: $x = \frac{7 + 11}{2} = \frac{18}{2} = 9 \Rightarrow \boxed{x = 9}$
• You can verify: $2 \cdot 9 = 18 \equiv 7 \pmod{11}$

✅ So the solution is $x \equiv 9 \pmod{11}$

---

Example 2: $7x \equiv 4 \pmod{11}$

Write:

$$ 7x = 4 + 11k \Rightarrow x = \frac{4 + 11k}{7} $$

Try values of $k$ and look for integer $x$:

• $k = 3$: $x = \frac{4 + 33}{7} = \frac{37}{7} \notin \mathbb{Z}$
• $k = 2$: $x = \frac{4 + 22}{7} = \frac{26}{7}$
• $k = 1$: $x = \frac{4 + 11}{7} = \frac{15}{7}$
• $k = 5$: $x = \frac{4 + 55}{7} = \frac{59}{7}$
• $k = 6$: $x = \frac{4 + 66}{7} = \frac{70}{7} = 10 \Rightarrow \boxed{x = 10}$

Verify: $7 \cdot 10 = 70 \equiv 4 \pmod{11}$

✅ So the solution is $x \equiv 10 \pmod{11}$

---

Example 3: $x^5 \equiv 3 \pmod{4}$

Write:

$$ x^5 = 3 + 4k \Rightarrow x = \sqrt[5]{3 + 4k} $$

Try small integer values of $k$ and check if the 5th root is an integer:

• $k = 0$: $x^5 = 3 \Rightarrow x = \sqrt[5]{3}$ ❌
• $k = 1$: $x^5 = 7 \Rightarrow x = \sqrt[5]{7}$ ❌
• $k = 2$: $x^5 = 11$ ❌
• $k = 3$: $x^5 = 15$ ❌
• $k = 4$: $x^5 = 19$
• $k = 5$: $x^5 = 23$
• $k = 6$: $x^5 = 27 \Rightarrow x = 3 \Rightarrow \boxed{x = 3}$

Verify: $3^5 = 243 \equiv 3 \pmod{4}$

✅ So $x \equiv 3 \pmod{4}$

---

🧠 Summary

To convert congruences into real equations (for calculators):

1. Rewrite the congruence $a \equiv b \pmod{n}$ as $a = b + kn$ where $k \in \mathbb{Z}$.
2. Solve the resulting real-number equation for $x$.
3. Try small integer values of $k$ to find valid (integer) solutions for $x$.

Let me know if you want a method that avoids brute-force trial for $k$.

Is there one?

Yes — instead of trial and error, there's a systematic method based on modular inverses, which avoids guessing values of $k$. Here's how it works:

---

🔄 Method: Use Modular Inverses (no guessing)

Idea:

To solve a linear congruence like:

$$ ax \equiv b \pmod{n} $$

You can multiply both sides by the modular inverse of $a \mod n$ — provided the inverse exists (i.e., $\gcd(a, n) = 1$).

---

🔁 Step-by-step

Step 1: Find the modular inverse of $a \mod n$

Let $a^{-1}$ be the modular inverse of $a \mod n$, meaning:

$$ a \cdot a^{-1} \equiv 1 \pmod{n} $$

Step 2: Multiply both sides by $a^{-1}$

$$ a^{-1} \cdot ax \equiv a^{-1} \cdot b \pmod{n} \Rightarrow x \equiv a^{-1} b \pmod{n} $$

---

✅ Examples

Example 1: $2x \equiv 7 \pmod{11}$

• Find $2^{-1} \mod 11$

We need $2y \equiv 1 \pmod{11}$. Try small values:

• $y = 6 \Rightarrow 2 \cdot 6 = 12 \equiv 1 \pmod{11}$

So $2^{-1} = 6 \mod{11}$

Then:

$$ x \equiv 6 \cdot 7 = 42 \equiv \boxed{9 \pmod{11}} $$

No trial and error needed!

---

Example 2: $7x \equiv 4 \pmod{11}$

• Find $7^{-1} \mod 11$

Try:

• $7 \cdot 8 = 56 \equiv 1 \pmod{11}$

So $7^{-1} = 8 \mod 11$

Then:

$$ x \equiv 8 \cdot 4 = 32 \equiv \boxed{10 \pmod{11}} $$

---

⚠️ Note on Higher Powers

This method is mainly for linear congruences (like $ax \equiv b \mod n$).

For nonlinear ones like:

• $x^5 \equiv 3 \mod 4$

you generally:

• Try all values of $x \mod 4$, since there are only 4: $0, 1, 2, 3$
• Compute $x^5 \mod 4$ for each

Example:

• $x = 0 \Rightarrow 0^5 = 0 \mod 4$
• $x = 1 \Rightarrow 1^5 = 1$
• $x = 2 \Rightarrow 32 \equiv 0 \mod 4$
• $x = 3 \Rightarrow 243 \equiv 3 \mod 4$

✅ So $x \equiv 3 \pmod{4}$ is the solution

---

💡 Summary

Type	Method
Linear congruence $ax \equiv b \mod n$	Multiply both sides by $a^{-1} \mod n$
Power congruence $x^k \equiv b \mod n$	Try all $x \in \{0, 1, ..., n-1\}$ or use discrete logs (advanced)

Let me know if you want help finding modular inverses programmatically or using the Extended Euclidean Algorithm.