Linear Congruence Equation

This article discusses how to solve linear congruence equations.

Basic Concepts

Let $a,b,n$ be integers and $x$ an unknown. An equation of the form

is called a linear congruence equation (linear congruence equation).

To solve a linear congruence equation, we need to find all solutions for $x$ in the interval $[0,n-1]$. Of course, adding or subtracting any multiple of $n$ from them still gives a solution to the equation. In the sense of modulo $n$, these are all the solutions to the equation.

This article introduces two approaches to solving linear congruence equations, using inverses and Diophantine equations respectively. In general, solving both inverses and Diophantine equations requires the extended Euclidean algorithm, so these two approaches are actually consistent.

Solving with an Inverse

First, consider the case where $a$ and $n$ are coprime, that is, $\gcd(a,n)=1$. In this case, we can calculate the inverse $a^{-1}$ of $a$ and multiply both sides of the equation by $a^{-1}$, obtaining the unique solution:

Next, consider the case where $a$ and $n$ are not coprime, that is, $\gcd(a,n)=d>1$. In this case, the original equation may not have a solution. For example, $2x\equiv 1\pmod 4$ has no solution. Therefore, two cases need to be considered:

• When $d$ does not divide $b$, the equation has no solution. For any $x$, the left-hand side $ax$ is a multiple of $d$, but the right-hand side $b$ is not a multiple of $d$. Therefore, they cannot differ by a multiple of $n$, because any multiple of $n$ must also be a multiple of $d$. Thus, the equation has no solution.

• When $d$ divides $b$, divide all three parameters $a,b,n$ in the equation by $d$ to obtain a new equation:

  $$a'x \equiv b'\pmod{n'}.$$

  Here, $\gcd(a',n')=1$, which means that $a'$ and $n'$ are coprime. This case was solved above, so a solution $x'$ to the equation can be obtained by finding an inverse.

  Clearly, $x'$ is also a solution to the original equation. However, it is not the only solution to the original equation. Since the complete set of solutions to the transformed equation is

  $$\{x' + kn' : k\in\mathbf Z\}.$$

  Among these solutions, those in the interval $[0,n-1]$ are exactly all the solutions to the original equation in the interval $[0,n-1]$:

  $$x \equiv (x' + kn')\pmod{n},\quad k = 0, 1, \cdots, d-1.$$

Summarizing these two cases, the number of solutions to a linear congruence equation is $d=\gcd(a,n)$ or $0$.

Solving with a Diophantine Equation

A linear congruence equation is equivalent to the binary linear Diophantine equation in $x,y$:

Using the discussion on the referenced page, the equation has a solution if and only if $\gcd(a,n)\mid b$, and one general solution to the equation is

where $d=\gcd(a,n)$ is their greatest common divisor and $t$ is any integer.

Consequently, the general solution to the linear congruence equation is

Taking $x_0$ modulo $n/d$ gives the smallest (nonnegative) integer solution to the congruence equation, namely the $x'$ above.

Reference Implementation

The reference implementations in this section obtain the smallest nonnegative integer solution to the congruence equation. If no solution exists, they output $-1$.

// Extended Euclidean Algorithm.
// Finds integers x, y such that a*x + b*y = gcd(a, b),
// and returns gcd(a, b).
int ex_gcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  } else {
    int d = ex_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
  }
}

// Solves the linear congruence equation:
//     a * x ≡ b (mod n), where n > 0.
// Returns the smallest non-negative solution x,
// or -1 if there is no solution.
int solve_linear_congruence_equation(int a, int b, int n) {
  int x, y;
  int d = ex_gcd(a, n, x, y);
  if (b % d) return -1;
  n /= d;
  return ((long long)x * (b / d) % n + n) % n;
}

def ex_gcd(a, b):
    """
    Extended Euclidean Algorithm.
    Finds integers x, y such that a*x + b*y = gcd(a, b),
    and returns (gcd, x, y).
    """
    if b == 0:
        return a, 1, 0
    d, x1, y1 = ex_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return d, x, y


def solve_linear_congruence_equation(a, b, n):
    """
    Solves the linear congruence equation:
        a * x ≡ b (mod n), where n > 0.
    Returns the smallest non-negative solution x,
    or -1 if there is no solution.
    """
    d, x, y = ex_gcd(a, n)
    if b % d != 0:
        return -1
    n //= d
    return (x * (b // d) % n + n) % n

Exercises

• “NOIP2012” Congruence Equation

This page is mainly translated from the blog post Модульное линейное уравнение первого порядка and its English translation Linear Congruence Equation. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0. The content has been modified.