18.15 Linear Congruences

A linear congruence is the modular analogue of a linear equation. Instead of solving

ax = b

over the integers or real numbers, we solve

ax ≡ b (mod m)

over residue classes. This problem appears in modular division, cyclic scheduling, cryptography, Diophantine equations, calendar arithmetic, and many CRT-based algorithms.

The main difference from ordinary algebra is that division is not always valid. The coefficient a may or may not have an inverse modulo m. The Euclidean Algorithm determines exactly when solutions exist and how many there are.

Problem

Given integers:

a
b
m

solve:

ax ≡ b (mod m)

Find all residue classes x modulo m that satisfy the congruence.

Example:

3x ≡ 6 (mod 9)

Testing values gives:

x = 2, 5, 8

because:

3×2 = 6
3×5 = 15 ≡ 6 (mod 9)
3×8 = 24 ≡ 6 (mod 9)

There are three solutions modulo 9.

Convert to a Diophantine Equation

The congruence:

ax ≡ b (mod m)

means:

m | (ax - b)

So there exists an integer y such that:

ax - b = my

Rearrange:

ax - my = b

Equivalently:

ax + mY = b

where Y = -y.

Thus a linear congruence is the same as a linear Diophantine equation:

ax + mY = b

This immediately gives the solvability criterion.

Solvability Criterion

The equation:

ax ≡ b (mod m)

has a solution if and only if:

gcd(a,m) | b

Let:

g = gcd(a,m)

If g does not divide b, no solution exists.

Example with no solution:

6x ≡ 5 (mod 10)

Here:

gcd(6,10) = 2

but:

2 ∤ 5

So no solution exists.

Example with solutions:

6x ≡ 4 (mod 10)

Here:

gcd(6,10) = 2

and:

2 | 4

So solutions exist.

Reducing the Congruence

If:

g = gcd(a,m)

and g | b, divide all three values by g:

a' = a / g
b' = b / g
m' = m / g

Then solve:

a'x ≡ b' (mod m')

Now:

gcd(a',m') = 1

so a' has a modular inverse modulo m'.

The reduced solution is:

x ≡ b' × (a')⁻¹ (mod m')

This gives one residue class modulo m'. In the original modulus m, it expands to g solutions.

Example

Solve:

6x ≡ 4 (mod 10)

Compute:

g = gcd(6,10) = 2

Since:

2 | 4

solutions exist.

Divide by 2:

3x ≡ 2 (mod 5)

The inverse of 3 modulo 5 is 2, because:

3 × 2 ≡ 1 (mod 5)

Thus:

x ≡ 2 × 2 ≡ 4 (mod 5)

Modulo 10, this gives:

x = 4
x = 9

Check:

6 × 4 = 24 ≡ 4 (mod 10)
6 × 9 = 54 ≡ 4 (mod 10)

Both are valid.

General Solution

If:

ax ≡ b (mod m)

has solutions and:

g = gcd(a,m)

then there are exactly g solutions modulo m.

After solving the reduced congruence:

x ≡ x₀ (mod m/g)

the solutions modulo m are:

x = x₀ + k(m/g)

for:

k = 0, 1, ..., g-1

This gives all distinct solutions modulo m.

Implementation

First define Extended Euclid and modular inverse.

from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    g, x1, y1 = extended_gcd(b, a % b)

    x = y1
    y = x1 - (a // b) * y1

    return g, x, y

def mod_inverse(a, m):
    g, x, _ = extended_gcd(a, m)

    if g != 1:
        raise ValueError("inverse does not exist")

    return x % m

Now solve the linear congruence.

def solve_linear_congruence(a, b, m):
    g = gcd(a, m)

    if b % g != 0:
        return []

    a_reduced = a // g
    b_reduced = b // g
    m_reduced = m // g

    inv = mod_inverse(a_reduced, m_reduced)
    x0 = (b_reduced * inv) % m_reduced

    solutions = []

    for k in range(g):
        solutions.append((x0 + k * m_reduced) % m)

    return sorted(solutions)

Example:

print(solve_linear_congruence(6, 4, 10))

Output:

[4, 9]

Solving When gcd(a, m) = 1

The simplest case occurs when a and m are coprime.

Then:

gcd(a,m)=1

and there is exactly one solution modulo m.

The solution is:

x ≡ b × a⁻¹ (mod m)

Example:

7x ≡ 3 (mod 26)

Since:

gcd(7,26)=1

there is one solution.

The inverse of 7 modulo 26 is 15.

Therefore:

x ≡ 3 × 15 ≡ 45 ≡ 19 (mod 26)

Check:

7 × 19 = 133
133 mod 26 = 3

Multiple Solutions

Consider:

4x ≡ 8 (mod 12)

Here:

g = gcd(4,12)=4

and:

4 | 8

Divide:

x ≡ 2 (mod 3)

Modulo 12, this expands to:

Check:

4×2  = 8  ≡ 8 (mod 12)
4×5  = 20 ≡ 8 (mod 12)
4×8  = 32 ≡ 8 (mod 12)
4×11 = 44 ≡ 8 (mod 12)

There are exactly four solutions modulo 12.

No Solution Case

Consider:

4x ≡ 7 (mod 12)

Here:

gcd(4,12)=4

but:

4 ∤ 7

No integer x can satisfy the congruence.

This is the most important guard condition in implementation.

Normalizing Inputs

The same congruence may be written with negative or large coefficients.

Examples:

-3x ≡ 4 (mod 7)

Normalize:

-3 ≡ 4 (mod 7)

so solve:

4x ≡ 4 (mod 7)

Similarly:

20x ≡ 13 (mod 7)

becomes:

6x ≡ 6 (mod 7)

In code:

a %= m
b %= m

before solving. This usually simplifies the arithmetic.

Counting Solutions in a Range

Sometimes the task asks for solutions in an interval:

L ≤ x ≤ R

not just residue classes modulo m.

If the solution class is:

x ≡ x₀ (mod q)

then all solutions are:

x = x₀ + tq

Count integers t satisfying:

L ≤ x₀ + tq ≤ R

Implementation:

def ceil_div(a, b):
    return -((-a) // b)

def floor_div(a, b):
    return a // b

def count_in_range(x0, step, left, right):
    t_min = ceil_div(left - x0, step)
    t_max = floor_div(right - x0, step)

    return max(0, t_max - t_min + 1)

This pattern appears in scheduling, periodic event counting, and integer constraint problems.

Application: Modular Division

The congruence:

ax ≡ b (mod m)

is exactly the problem of dividing b by a modulo m.

When gcd(a,m)=1, modular division has a unique answer.

When gcd(a,m)>1, there may be no answer or multiple answers.

This is why modular division requires more care than modular multiplication.

Application: Cyclic Scheduling

Suppose a machine performs a task every m minutes. We want to find a time x such that:

ax ≡ b (mod m)

This can model repeated jumps around a cycle. If the jump size a and cycle size m share a common divisor, only some positions are reachable.

The same criterion applies:

gcd(a,m) | b

Reachability in a cycle is a linear congruence.

Common Mistakes

Dividing Without Checking gcd

This is wrong:

6x ≡ 4 (mod 10)

Directly dividing by 6 is invalid because 6 has no inverse modulo 10.

Returning Only One Solution

If gcd(a,m)>1, there may be multiple solutions modulo m.

Return all residue classes when the problem asks for all solutions.

Forgetting the No-Solution Case

If gcd(a,m) does not divide b, there is no solution.

Mixing Moduli

After reduction, the first solution is modulo:

m/g

The expanded solution set belongs modulo:

Keep these two moduli separate.

Mishandling Negative Inputs

Normalize coefficients and remainders before solving, or make sure your language's modulo behavior is well understood.

Testing

Basic tests:

def test_linear_congruence():
    assert solve_linear_congruence(6, 4, 10) == [4, 9]
    assert solve_linear_congruence(4, 8, 12) == [2, 5, 8, 11]
    assert solve_linear_congruence(4, 7, 12) == []
    assert solve_linear_congruence(7, 3, 26) == [19]

A property test can verify each returned solution:

def test_solutions_are_valid():
    cases = [
        (6, 4, 10),
        (4, 8, 12),
        (7, 3, 26),
        (15, 10, 35),
    ]

    for a, b, m in cases:
        for x in solve_linear_congruence(a, b, m):
            assert (a * x - b) % m == 0

Also verify completeness for small moduli by brute force:

def brute_solutions(a, b, m):
    return [x for x in range(m) if (a * x - b) % m == 0]

def test_against_brute_force():
    for m in range(1, 50):
        for a in range(-50, 51):
            for b in range(-50, 51):
                assert solve_linear_congruence(a, b, m) == brute_solutions(a, b, m)

This catches edge cases around zero, repeated solutions, and negative inputs.

Takeaway

A linear congruence ax ≡ b (mod m) is solvable exactly when gcd(a,m) divides b. After dividing by this gcd, the reduced coefficient is invertible, yielding one solution modulo m/g. Expanding that solution gives exactly g solutions modulo m. This framework turns modular division, cyclic reachability, scheduling constraints, and many Diophantine problems into a small, reliable algorithm built on the Extended Euclidean Algorithm.