Methods and Techniques for Solving Congruences
There are several approaches to solving a congruence equation of the form:
$$ ax \equiv b \pmod{m} $$
Here are the most common ones:
The Modular Inverse Method
If the coefficient \( a \) has a multiplicative inverse modulo \( m \)—that is, if \( \gcd(a, m) = 1 \)—then there exists an inverse \( a^{-1} \) modulo \( m \). In this case, we can multiply both sides of the equation by \( a^{-1} \) to isolate \( x \):
\[
x \equiv a^{-1} b \pmod{m}
\]
The modular inverse \( a^{-1} \) can be found using the extended Euclidean algorithm.
Example
Let’s solve the congruence:
\[ 7x \equiv 5 \pmod{13} \]
First, we check whether \(7\) is invertible modulo \(13\).
A number has an inverse modulo \( m \) if it is coprime with \( m \), meaning that \(\gcd(7, 13) = 1\).
Since \(7\) and \(13\) are relatively prime, \(7\) does indeed have an inverse modulo \(13\).
Now, we need to compute the modular inverse of \(7\) modulo \(13\).
The modular inverse of \(7\) is a number \(7^{-1}\) that satisfies:
$$ 7 \cdot 7^{-1} \equiv 1 \pmod{13} $$
To determine \(7^{-1}\), we use the extended Euclidean algorithm to solve:
\[ 7y \equiv 1 \pmod{13} \]
Applying Bézout’s identity for \(7\) and \(13\):
\[ 13 = 1 \cdot 7 + 6 \]
\[ 7 = 1 \cdot 6 + 1 \]
\[ 6 = 6 \cdot 1 + 0 \]
Working backward:
\[ 1 = 7 - 1 \cdot 6 \]
Substituting \(6 = 13 - 1 \cdot 7\):
\[ 1 = 7 - (13 - 1 \cdot 7) \]
\[ 1 = 7 - 13 + 7 \]
\[ 1 = 2 \cdot 7 - 13 \]
So the modular inverse of \(7\) modulo \(13\) is \(2\).
\[ 7^{-1} \equiv 2 \pmod{13} \]
Now that we have the inverse, we multiply both sides of the original congruence by \(7^{-1} = 2\):
\[ 2 \cdot (7x) \equiv 2 \cdot 5 \pmod{13} \]
\[ (2 \cdot 7)x \equiv 10 \pmod{13} \]
Since \(2 \cdot 7 = 14 \equiv 1 \pmod{13}\), we get:
\[ x \equiv 10 \pmod{13} \]
Thus, the solution to the congruence is \( x = 10 \).
Reducing by the Greatest Common Divisor
If \( \gcd(a, m) = d > 1 \), the congruence equation has solutions if and only if \( d \) divides \( b \). When this condition holds, we can divide everything by \( d \), simplifying the equation to an equivalent congruence modulo \( m/d \).
Example
Consider the congruence:
\[ 6x \equiv 9 \pmod{15} \]
First, we compute the greatest common divisor:
\[ \gcd(6, 15) = 3 \]
Since \( \gcd(6, 15) \) divides \( 9 \), the congruence has solutions.
If it didn’t, no solutions would exist.
Now, we divide both sides by \( \gcd(6, 15) = 3 \):
\[ \frac{6}{3} x \equiv \frac{9}{3} \pmod{\frac{15}{3}} \]
\[ 2x \equiv 3 \pmod{5} \]
This simplifies the problem to a more manageable congruence.
Next, we need to find the modular inverse of \(2\) modulo \(5\), which is a number \( y \) such that:
\[ 2y \equiv 1 \pmod{5} \]
Since the modulus is small, we can simply test values:
- \( 2 \cdot 1 = 2 \not\equiv 1 \pmod{5} \)
- \( 2 \cdot 2 = 4 \not\equiv 1 \pmod{5} \)
- \( 2 \cdot 3 = 6 \equiv 1 \pmod{5} \) ✅
Thus, the modular inverse of \( 2 \) modulo \( 5 \) is \( 2^{-1} \equiv 3 \pmod{5} \).
We multiply both sides of the congruence by \(3\):
\[ (3 \cdot 2) x \equiv 3 \cdot 3 \pmod{5} \]
\[ 6x \equiv 9 \pmod{5} \]
Since \(6 \equiv 1 \pmod{5}\) and \(9 \equiv 4 \pmod{5}\), we get:
\[ x \equiv 4 \pmod{5} \]
This means the congruence has infinitely many solutions of the form:
\[ x = 4 + 5k, \quad k \in \mathbb{Z} \]
Among these, the fundamental solution to the original congruence is \( x = 4 \).
Trial Substitution Method
For small moduli, a simple approach is to test values of \( x \) directly (brute force) until we find a solution.
Example
Consider the congruence:
\[ 3x \equiv 4 \pmod{7} \]
Since the modulus is small (\(7\)), we can check values \( x = 0, 1, 2, \dots, 6 \) manually.
Computing \( 3x \mod 7 \) for different values of \( x \):
- \( x = 0 \Rightarrow 3(0) = 0 \not\equiv 4 \pmod{7} \)
- \( x = 1 \Rightarrow 3(1) = 3 \not\equiv 4 \pmod{7} \)
- \( x = 2 \Rightarrow 3(2) = 6 \not\equiv 4 \pmod{7} \)
- \( x = 3 \Rightarrow 3(3) = 9 \equiv 2 \pmod{7} \)
- \( x = 4 \Rightarrow 3(4) = 12 \equiv 5 \pmod{7} \)
- \( x = 5 \Rightarrow 3(5) = 15 \equiv 1 \pmod{7} \)
- \( x = 6 \Rightarrow 3(6) = 18 \equiv 4 \pmod{7} \) ✅
We found that \( x = 6 \) satisfies the congruence:
\[ 3x \equiv 4 \pmod{7} \]
\[ 3 \cdot 6 \equiv 4 \pmod{7} \]
\[ 18 \equiv 4 \pmod{7} \]
Thus, the fundamental solution is \( x = 6 \), and the general solution is:
\[ x = 6 + 7k, \quad k \in \mathbb{Z} \]
Factorizing the Modulus
When the modulus \( m \) can be factored into prime powers as \( m = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n} \), we can apply the Chinese Remainder Theorem to break the original congruence into a system of simpler congruences modulo the prime factors of \( m \).
Example
Consider the congruence:
\[ 34x \equiv 12 \pmod{77} \]
Since \( 77 \) factors as:
\[ 77 = 7 \times 11 \]
we can rewrite the congruence as a system of two modular equations:
\[ \begin{cases} 34x \equiv 12 \pmod{7} \\ \\ 34x \equiv 12 \pmod{11} \end{cases} \]
Step 1: Simplify Each Congruence
We reduce each equation modulo \( 7 \) and \( 11 \):
\( 34 \equiv 6 \pmod{7} \) and \( 12 \equiv 5 \pmod{7} \), so the first congruence simplifies to:
\[ \begin{cases} 6x \equiv 5 \pmod{7} \\ \\ 34x \equiv 12 \pmod{11} \end{cases} \]
\( 34 \equiv 1 \pmod{11} \) and \( 12 \equiv 1 \pmod{11} \), so the second congruence simplifies to:
\[ \begin{cases} 6x \equiv 5 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]
Step 2: Solve \( 6x \equiv 5 \pmod{7} \)
To solve \( 6x \equiv 5 \pmod{7} \), we first find the modular inverse of \( 6 \) modulo \( 7 \), which is a number \( y \) such that:
\[ 6y \equiv 1 \pmod{7} \]
Testing values:
- \( 6 \cdot 1 \equiv 6 \pmod{7} \)
- \( 6 \cdot 2 \equiv 12 \equiv 5 \pmod{7} \)
- \( 6 \cdot 3 \equiv 18 \equiv 4 \pmod{7} \)
- \( 6 \cdot 4 \equiv 24 \equiv 3 \pmod{7} \)
- \( 6 \cdot 5 \equiv 30 \equiv 2 \pmod{7} \)
- \( 6 \cdot 6 \equiv 36 \equiv 1 \pmod{7} \) ✅
So the modular inverse is \( 6^{-1} \equiv 6 \pmod{7} \).
Multiplying both sides of \( 6x \equiv 5 \pmod{7} \) by \( 6^{-1} = 6 \):
\[ \begin{cases} 6x \cdot 6 \equiv 5 \cdot 6 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]
\[ \begin{cases} 36x \equiv 30 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]
Since \( 36 \equiv 1 \pmod{7} \) and \( 30 \equiv 2 \pmod{7} \), we get:
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]
Step 3: Solve the System
We now have:
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]
Express \( x \) from the first equation:
\[ x = 2 + 7k, \quad k \in \mathbb{Z} \]
Substituting into the second equation:
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 2+7k \equiv 1 \pmod{11} \end{cases} \]
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 2+7k -2 \equiv 1 -2 \pmod{11} \end{cases} \]
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 7k \equiv -1 \pmod{11} \end{cases} \]
Since \( -1 \equiv 10 \pmod{11} \), we rewrite it as:
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 7k \equiv 10 \pmod{11} \end{cases} \]
Step 4: Solve for \( k \)
To solve \( 7k \equiv 10 \pmod{11} \), we find the modular inverse of \( 7 \) modulo \( 11 \), i.e., a number \( 7^{-1} \) such that:
\[ 7 \cdot 7^{-1} \equiv 1 \pmod{11} \]
Testing values:
- \( 7 \cdot 1 \equiv 7 \pmod{11} \)
- \( 7 \cdot 2 \equiv 14 \equiv 3 \pmod{11} \)
- \( 7 \cdot 3 \equiv 21 \equiv 10 \pmod{11} \)
- \( 7 \cdot 8 \equiv 56 \equiv 1 \pmod{11} \) ✅
So, \( 7^{-1} \equiv 8 \pmod{11} \).
Multiplying both sides of \( 7k \equiv 10 \pmod{11} \) by \( 8 \):
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 7k \cdot 8 \equiv 10 \cdot 8 \pmod{11} \end{cases} \]
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ 56k \equiv 80 \pmod{11} \end{cases} \]
Since \( 56 \equiv 1 \pmod{11} \) and \( 80 \equiv 3 \pmod{11} \), we get:
\[ \begin{cases} x \equiv 2 \pmod{7} \\ \\ k \equiv 3 \pmod{11} \end{cases} \]
This means:
\[ k = 3 + 11m, \quad m \in \mathbb{Z} \]
Final Solution
Substituting \( k \) into \( x = 2 + 7k \):
\[ x = 2 + 7(3 + 11m) \]
\[ x = 2 + 21 + 77m \]
\[ x = 23 + 77m \]
which gives the general solution:
$$ x \equiv 23 \pmod{77} $$
Verification
Substituting \( x = 23 \) into the original congruence:
\[ 34x \equiv 12 \pmod{77} \]
\[ 34 \cdot 23 \equiv 12 \pmod{77} \]
\[ 782 \equiv 12 \pmod{77} \]
\[ 12 \equiv 12 \pmod{77} \]
This confirms the solution is correct. By using the Chinese Remainder Theorem, we were able to break down the original congruence into two simpler ones and reconstruct the solution efficiently.
Successive Squaring Method
When solving a congruence of the form:
$$ x^k \equiv b \pmod{m} $$
we can use Euler-Fermat’s theorem or specialized algorithms such as the Tonelli-Shanks method for modular square roots when \( p \) is prime.
The successive squaring method involves the following steps:
- Reduce the exponent modulo \( \varphi(m) \)
- If \( m \) is prime, we apply Fermat’s little theorem:
\[ x^{p-1} \equiv 1 \pmod{p} \].
- If \( m \) is composite, we use Euler’s theorem:
\[ x^{\varphi(m)} \equiv 1 \pmod{m} \] where \( \varphi(m) \) is the Euler totient function. - Reduce the exponent \( k \) modulo \( \varphi(m) \)
- If \( k \) is large, compute \( k \mod \varphi(m) \) to simplify exponentiation. - Use efficient modular exponentiation
- Compute \( x^k \) using fast exponentiation (binary exponentiation) to avoid handling excessively large numbers. - Solve for \( x \), if necessary
- If the equation takes the form \( x^k \equiv b \pmod{m} \), finding \( x \) may require solving a discrete logarithm. Algorithms such as Tonelli-Shanks (for square roots \( x^2 \equiv b \pmod{p} \)) or the Baby-step Giant-step method (for larger exponents when \( m \) is prime) can be used.
We’ll go through two examples: one where the modulus is prime and another where it is composite.
Example
Consider the congruence:
\[ x^5 \equiv 3 \pmod{7} \]
Since \( m = 7 \) is prime, we apply Fermat’s theorem, which states that for any integer \( a \) not divisible by \( 7 \):
\[ a^{6} \equiv 1 \pmod{7} \]
This implies that any exponent can be reduced modulo 6, since powers of any number modulo 7 cycle every 6 steps.
For example, let’s compute the powers of \( x = 3 \) modulo 7:
- \( 3^1 \equiv 3 \pmod{7} \)
- \( 3^2 \equiv 2 \pmod{7} \)
- \( 3^3 \equiv 6 \pmod{7} \)
- \( 3^4 \equiv 4 \pmod{7} \)
- \( 3^5 \equiv 5 \pmod{7} \)
- \( 3^6 \equiv 1 \pmod{7} \) ✅
Since \( 3^6 \equiv 1 \pmod{7} \), all subsequent powers repeat this cycle. For instance, \( 3^7 \equiv 3^6 \cdot 3 \equiv 3 \pmod{7} \), matching \( 3^1 \equiv 3 \pmod{7} \). This confirms that the cycle repeats every 6 steps, as predicted by Fermat’s theorem.
Step 1: Isolating \( x \)
To solve for \( x \), we need to eliminate the exponent 5.
A convenient way to do this is by finding the modular inverse of 5 modulo 6, denoted \( d = 5^{-1} \), such that:
$$ 5d \equiv 1 \pmod{6} $$
Then, raising both sides of the congruence to this power gives:
\[ (x^5)^d \equiv 3^d \pmod{7} \]
Step 2: Computing the Modular Inverse
We find \( d \) such that \( 5d \equiv 1 \pmod{6} \):
- \( 5 \cdot 1 \equiv 5 \pmod{6} \)
- \( 5 \cdot 2 \equiv 4 \pmod{6} \)
- \( 5 \cdot 3 \equiv 3 \pmod{6} \)
- \( 5 \cdot 4 \equiv 2 \pmod{6} \)
- \( 5 \cdot 5 \equiv 1 \pmod{6} \) ✅
Thus, \( d = 5 \).
Note: Another way to find the modular inverse is by solving the Diophantine equation: \[ 5d \equiv 1 \pmod{6} \] Using the Extended Euclidean Algorithm, we express the greatest common divisor as: \[ 6 = 5 \cdot 1 + 1 \] Rearranging, we obtain: \[ 1 = 6 - 5 \cdot 1 \] which gives: \[ d \equiv -1 \equiv 5 \pmod{6} \] Thus, the modular inverse of 5 modulo 6 is \( 5 \).
Step 3: Raising Both Sides to the Fifth Power
Now we exponentiate both sides:
\[ (x^5)^5 \equiv 3^5 \pmod{7} \]
\[ x^{25} \equiv 3^5 \pmod{7} \]
Step 4: Reducing the Exponent
Using Fermat’s theorem, \( x^6 \equiv 1 \pmod{7} \), so we reduce \( 25 \) modulo 6:
\[ x^{25} = x^{6 \cdot 4 + 1} \]
\[ (x^6)^4 \cdot x \equiv 3^5 \pmod{7} \]
Since \( x^6 \equiv 1 \pmod{7} \), this simplifies to:
\[ (1)^4 \cdot x \equiv 3^5 \pmod{7} \]
\[ x \equiv 3^5 \pmod{7} \]
Step 5: Computing \( 3^5 \mod{7} \)
Since \( 3^5 = (3^2)^2 \cdot 3 \), we compute:
\( 3^2 = 9 \equiv 2 \pmod{7} \)
\[ x \equiv 2 \cdot 2 \cdot 3 \pmod{7} \]
\[ x \equiv 12 \pmod{7} \]
\[ x \equiv 5 \pmod{7} \]
Final Answer
Thus, \( x = 5 \) is the solution to the original congruence.
Alternative Approach: We could also compute \( x \equiv 3^5 \pmod{7} \) directly: \[ x \equiv 243 \pmod{7} \] Since \( 243 \div 7 = 34 \) remainder \( 5 \), we obtain: \[ x \equiv 5 \pmod{7} \] confirming our previous result.
Example 2
Let's solve the congruence:
\[ x^5 \equiv 3 \pmod{14} \]
Since the modulus \( 14 \) is composite (\( 14 = 2 \cdot 7 \)), we use the Euler totient function:
\[ \varphi(14) = (2 - 1)(7 - 1) = 1 \times 6 = 6 \]
By Euler’s theorem, for any integer \( a \) coprime to 14:
\[ a^6 \equiv 1 \pmod{14} \]
This means exponents can be reduced modulo 6, since powers of any number modulo 14 cycle every 6 steps.
Step 1: Finding the Modular Inverse of 5
To isolate \( x \), we raise both sides of the congruence to the modular inverse \( d \) of the exponent 5:
\[ (x^5)^d \equiv 3^d \pmod{14} \]
We need to find \( d \) such that:
\[ 5d \equiv 1 \pmod{6} \]
Testing values:
- \( 5 \times 1 \equiv 5 \pmod{6} \)
- \( 5 \times 2 \equiv 4 \pmod{6} \)
- \( 5 \times 3 \equiv 3 \pmod{6} \)
- \( 5 \times 4 \equiv 2 \pmod{6} \)
- \( 5 \times 5 \equiv 1 \pmod{6} \) ✅
Thus, the modular inverse of \( 5 \) modulo \( 6 \) is \( d = 5 \).
Step 2: Raising Both Sides to the Fifth Power
Now, we exponentiate both sides by \( d = 5 \):
\[ (x^5)^5 \equiv 3^5 \pmod{14} \]
\[ x^{25} \equiv 3^5 \pmod{14} \]
Step 3: Reducing the Exponent
By Euler’s theorem, \( x^6 \equiv 1 \pmod{14} \), so we express 25 in terms of multiples of 6:
\[ 25 = 6 \cdot 4 + 1 \]
Rewriting the exponent:
\[ x^{6 \cdot 4 + 1} \equiv 3^5 \pmod{14} \]
\[ (x^6)^4 \cdot x \equiv 3^5 \pmod{14} \]
Since \( x^6 \equiv 1 \pmod{14} \), this simplifies to:
\[ (1)^4 \cdot x \equiv 3^5 \pmod{14} \]
\[ x \equiv 3^5 \pmod{14} \]
Step 4: Computing \( 3^5 \mod{14} \)
Now, we compute:
\[ 3^5 = 243 \]
Finding the remainder when dividing by 14:
\[ 243 \div 14 = 17 \text{ remainder } 5 \]
Thus:
\[ x \equiv 5 \pmod{14} \]
Final Answer
The solution to the original congruence is \( x = 5 \).
