Solving Linear Congruences

Hello again! In our previous lesson, you learned how to perform modular division, $(a / b) (mod p)$ , by transforming it into a multiplication with the modular inverse. This was a crucial step, but it came with a key assumption: the modulus $p$ had to be prime. Today, we generalize this concept to solve equations of the form $a x \equiv b (mod m)$ , known as linear congruences.

This lesson tackles the problem for any modulus $m$ , prime or composite, and situations where the relationship between $a$ and $m$ is more complex. You'll learn when solutions exist, how many there are, and a systematic method to find them. This skill is essential for a wide range of competitive programming problems that go beyond the ideal conditions of prime moduli.

From Modular Division to Linear Congruences

In the last lesson, when you calculated $(b / a) (mod p)$ , you were implicitly finding a number $x$ such that $x \equiv b \cdot a^{- 1} (mod p)$ . If you multiply both sides by $a$ , you get $a x \equiv b (mod p)$ . So, modular division is just one specific case of solving a linear congruence where an inverse of $a$ is guaranteed to exist.

But what happens if $m$ is not prime, or if $a$ and $m$ share common factors? In these cases, the modular inverse $a^{- 1} (mod m)$ might not exist. Does that mean there's no solution? Not necessarily. The equation $a x \equiv b (mod m)$ provides a more powerful framework that can still have solutions.

Let's explore the general case. We are looking for all integer values of $x$ in the range $[0, m - 1]$ that satisfy the equation.

Conditions for a Solution

The first step is to determine if a solution even exists. An elegant rule governs this, based on the greatest common divisor (GCD) of $a$ and $m$ .

A linear congruence $a x \equiv b (mod m)$ has a solution if and only if $g cd (a, m)$ divides $b$ .

Why is this true? The expression $a x (mod m)$ means $a x - k m$ for some integer $k$ . Let $g = g cd (a, m)$ . Since $g$ divides both $a$ and $m$ , it must also divide any linear combination of them, including $a x - k m$ . Therefore, for the equation $a x - k m = b$ to hold, $g$ must also divide $b$ . If $b$ is not divisible by $g$ , no integer $x$ can satisfy the congruence.

Furthermore, if solutions do exist, there are exactly $g = g cd (a, m)$ distinct solutions modulo $m$ .

The following resource from cp-algorithms.com, a staple for competitive programmers, explains this condition clearly.

Linear Congruence Equation

This article provides a concise and clear explanation of solving linear congruences. It's perfectly suited for our competitive programming context.

Read the section titled "Solution by finding the inverse element." Pay close attention to the second half, starting from the case where a and n are not coprime. The key takeaways are the condition for no solution and the statement that the equation has exactly g solutions.

A Step-by-Step Method to Find All Solutions

Now that we know the conditions, let's establish a method to find the solutions. The strategy is to simplify the original congruence into one where an inverse does exist, find a single solution, and then use it to generate all other solutions.

Let $g = g cd (a, m)$ .

Check for Solvability: If $b$ is not divisible by $g$ , stop. There are no solutions.
Reduce the Congruence: If a solution exists, we can divide the entire congruence (all three parts: $a$ , $b$ , and $m$ ) by $g$ . This gives us a new, equivalent congruence:
$(a / g) x \equiv (b / g) (mod m / g)$
Let's call this $a^{'} x \equiv b^{'} (mod m^{'})$ . A crucial property is that now $g cd (a^{'}, m^{'}) = 1$ .
Find One Particular Solution ( $x_{0}$ ): Since $g cd (a^{'}, m^{'}) = 1$ , we know that $a^{'}$ has a modular multiplicative inverse modulo $m^{'}$ . We can solve for $x$ by multiplying both sides by this inverse:
$x \equiv b^{'} \cdot (a^{'})^{- 1} (mod m^{'})$
This gives us our first solution, which we'll call $x_{0}$ .
- How to find $(a^{'})^{- 1} (mod m^{'})$ ? If $m^{'}$ is prime, you can use Fermat's Little Theorem as you learned before. If $m^{'}$ is composite (and $a^{'}, m^{'}$ are coprime), you need a more general method. The standard algorithm for this is the Extended Euclidean Algorithm, which we will cover in detail in our very next lesson! For now, if $m^{'}$ is small, you can find the inverse by inspection (i.e., testing small numbers).
Generate All Solutions: The original congruence has $g$ solutions. We have found one, $x_{0}$ , which is correct modulo $m^{'}$ . All solutions modulo $m$ are given by:
$x_{k} = x_{0} + k \cdot m^{'} for k = 0, 1, 2, \dots, g - 1$
This generates $g$ distinct solutions in the range $[0, m - 1]$ .

A Worked Example

Let's solidify this with an example. Watch this video from Michael Penn, which walks through solving 140x ≡ 56 (mod 252).

Number Theory | Linear Congruence Example 2

This video provides a clear, step-by-step walkthrough of solving a non-trivial linear congruence, perfectly illustrating the method we just outlined.

Watch the entire video. It's short and to the point. The initial analysis where he determines that solutions exist and how many there are using the GCD. The reduction step, where the original congruence is simplified by dividing by the GCD. Solving the reduced congruence by finding an inverse by inspection and getting the first solution, x = 4. Generating all solutions based on the first solution and the number of expected solutions.

Let's retrace the video's steps using our method:

Equation: $140 x \equiv 56 (mod 252)$
- $a = 140, b = 56, m = 252$
Step 1: Check Solvability
- You can use the Euclidean algorithm (from Module 1) to find $g = g cd (140, 252) = 28$ .
- Does 28 divide 56? Yes, $56 = 2 \cdot 28$ .
- Conclusion: There are exactly 28 solutions.
Step 2: Reduce the Congruence
- Divide $a, b, m$ by $g = 28$ .
- $a^{'} = 140/28 = 5$
- $b^{'} = 56/28 = 2$
- $m^{'} = 252/28 = 9$
- The new congruence is $5 x \equiv 2 (mod 9)$ .
Step 3: Find One Solution
- We need to find $5^{- 1} (mod 9)$ . Since 9 is small and composite, we can't use Fermat's Little Theorem. We test values: $5 \cdot 1 \equiv 5$ , $5 \cdot 2 = 10 \equiv 1$ . The inverse is 2.
- $x_{0} \equiv 2 \cdot (5^{- 1}) (mod 9) \equiv 2 \cdot 2 (mod 9) \equiv 4 (mod 9)$ .
- Our first solution is $x_{0} = 4$ .
Step 4: Generate All Solutions
- The solutions are of the form $x_{k} = x_{0} + k \cdot m^{'} = 4 + k \cdot 9$ , for $k = 0, \dots, 27$ .
- The solutions are: 4, 13, 22, 31, ..., 247.

Looking Ahead: The Master Key

Our method relies on finding the modular inverse $(a^{'})^{- 1} (mod m^{'})$ . As mentioned, this is simple for prime $m^{'}$ but requires a more powerful tool for composite $m^{'}$ . This tool is the Extended Euclidean Algorithm, which finds integer solutions to equations of the form $a x + b y = g cd (a, b)$ .

The linear congruence $a x \equiv b (mod m)$ can be rewritten as $a x + m y = b$ for some integer $y$ . This is a Linear Diophantine Equation, and the Extended Euclidean Algorithm is the fundamental method for solving it.

This video gives an excellent intuitive derivation, showing how the problem of finding an inverse or solving a congruence transforms into the ax + by = c form that the Extended Euclidean Algorithm solves.

Modulo Inverses, Linear Congruence and Chinese remainder theorem by first principles | Number Theory

This video connects the dots between congruences and the underlying Diophantine equations from first principles.

Watch the segment from linear congruence. The key idea is seeing how ax \equiv b \pmod m is transformed into the equation ax + ym = b, which is exactly the form solved by the algorithm you'll learn next.

While you'll learn the full algorithm in the next lesson, you can already solve many problems. In competitive programming, a simple brute-force approach is often sufficient if the modulus $m$ is small.




#include <iostream>
#include <vector>
#include <numeric> // For std::gcd in C++17

// In C++14 or earlier, you'd have to implement gcd yourself.
/*
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}
*/

void solve_linear_congruence(long long a, long long b, long long m) {
    a %= m;
    b %= m;
    
    // For competitive programming with small m, this is a valid strategy.
    std::vector<long long> solutions;
    for (long long x = 0; x < m; ++x) {
        if ((a * x) % m == b) {
            solutions.push_back(x);
        }
    }

    if (solutions.empty()) {
        std::cout << "No solutions." << std::endl;
    } else {
        std::cout << "Solutions: ";
        for (long long sol : solutions) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    // Example from the lesson: 140x ≡ 56 (mod 252)
    // The solutions are 4, 13, 22, ...
    solve_linear_congruence(140, 56, 252); 

    // Example with no solution: 2x ≡ 1 (mod 4)
    // gcd(2, 4) = 2, which does not divide 1.
    solve_linear_congruence(2, 1, 4);
    return 0;
}

This brute-force code simply checks every possible value of $x$ . It's too slow for large $m$ , but for $m$ up to $1 0^{6}$ or so, it can pass within time limits. The analytical method is always better and necessary for large moduli.

Conclusion

In this lesson, you've moved beyond the simple case of modular division and tackled the general problem of solving linear congruences.

Here are the key takeaways:

A linear congruence $a x \equiv b (mod m)$ has solutions if and only if $g cd (a, m)$ divides $b$ .
If solutions exist, there are exactly $g cd (a, m)$ distinct solutions modulo $m$ .
The general strategy is to reduce the congruence by dividing all parts by $g = g cd (a, m)$ , solve the simpler congruence, and then generate all solutions from the one you found.
Solving the reduced congruence requires finding a modular inverse, which you can do with Fermat's Little Theorem (if the new modulus is prime) or by inspection (if small).

You now have a complete conceptual map for solving these equations. The final missing piece is the efficient implementation for the hardest case: finding a modular inverse with a large, composite modulus. Our next lesson will give you that key by introducing the Extended Euclidean Algorithm, a cornerstone of number theory in competitive programming.