Skip to content

Linear Congruence Equations

This article discusses solving linear congruence equations.

Basic Concepts

Let \(a,b,n\) be integers, and \(x\) be an unknown variable. An equation of the form

\[ ax\equiv b\pmod n \]

is called a linear congruence equation.

Solving a linear congruence equation involves finding all solutions for \(x\) in the interval \([0,n-1]\). Of course, adding or subtracting any multiple of \(n\) from these solutions still yields valid solutions. Under modulo \(n\), these constitute all solutions of the equation.

This article introduces two approaches for solving linear congruence equations, utilizing modular inverses and indeterminate equations, respectively. In general, both modular inverses and solving indeterminate equations require the use of the Extended Euclidean Algorithm. Therefore, these two approaches are essentially consistent.

Solving Using Modular Inverses

First, consider the case where \(a\) and \(n\) are coprime, i.e., \(\gcd(a,n)=1\). In this case, we can compute the modular inverse \(a^{-1}\) of \(a\), multiply both sides of the equation by \(a^{-1}\), and obtain the unique solution:

\[ x \equiv ba^{-1} \pmod n. \]

Next, consider the case where \(a\) and \(n\) are not coprime, i.e., \(\gcd(a,n)=d>1\). In this scenario, the original equation may not have a solution. For example, \(2x\equiv 1\pmod 4\) has no solution. Therefore, we need to consider two subcases:

  • 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\). Consequently, they cannot differ by a multiple of \(n\), since any multiple of \(n\) is also a multiple of \(d\). Thus, the equation has no solution.

  • When \(d\) divides \(b\), we can divide all parameters \(a,b,n\) by \(d\) to obtain a new equation:

    \[ a'x \equiv b'\pmod{n'}. \]

    Here, \(\gcd(a',n')=1\), meaning \(a'\) and \(n'\) are coprime. This case has already been addressed above, so we can find a solution \(x'\) by computing the modular inverse.

    Clearly, \(x'\) is also a solution of the original equation. However, it is not the only solution. The complete set of solutions for the transformed equation is

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

    Among these, the solutions that lie within the interval \([0,n-1]\) constitute all solutions of the original equation in that interval:

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

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

Solving Using Indeterminate Equations

A linear congruence equation is equivalent to a linear indeterminate equation in \(x\) and \(y\):

\[ ax + ny = b. \]

Based on the discussion in the referenced page, the equation has a solution if and only if \(\gcd(a,n)\mid b\), and a general solution to this equation is

\[ \begin{aligned} x &= x_0 + t\dfrac{n}{d},\\ y &= y_0 - t\dfrac{a}{d}, \end{aligned} \]

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

\[ x \equiv \left(x_0+t\frac{n}{d}\right)\pmod{n},\quad t\in\mathbf Z. \]

Taking \(x_0\) modulo \(n/d\) yields the smallest non-negative integer solution of the congruence equation, which corresponds to \(x'\) mentioned above.

Reference Implementation

The reference implementation provided in this section returns the smallest non-negative integer solution of the congruence equation. If no solution exists, it outputs \(-1\).

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

This page is primarily 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.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用