Linear congruences and the Chinese remainder theorem

With congruences in hand we can solve equations. This lesson treats the simplest kind: linear equations in integers, linear congruences \(ax \equiv b \pmod n\), and systems of congruences with different moduli. The last of these leads to the Chinese remainder theorem, first stated in a third-century Chinese text and today used everywhere from calendar calculations to fast arithmetic in computer algebra and cryptography.

Linear Diophantine equations

A Diophantine equation is an equation whose solutions are required to be integers, named after Diophantus of Alexandria, who studied such problems around 250 CE. The simplest is the linear equation \[ax + by = c.\]

Theorem. Let \(a, b\) be integers, not both 0, and \(d = \gcd(a, b)\). The equation \(ax + by = c\) has an integer solution if and only if \(d \mid c\). If \((x_0, y_0)\) is one solution, then all solutions are \[x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t \in \mathbb{Z}.\]

Proof. If a solution exists, \(d\) divides \(ax + by = c\). Conversely, if \(c = dk\), Bézout gives \(ax' + by' = d\), and \((kx', ky')\) is a solution. For the general solution, it is easy to check that the formula gives solutions. If \((x, y)\) is any solution, subtract: \(a(x - x_0) = b(y_0 - y)\). Divide by \(d\): \((a/d)(x - x_0) = (b/d)(y_0 - y)\). Since \(a/d\) and \(b/d\) are coprime, Euclid's lemma gives \((b/d) \mid x - x_0\), say \(x - x_0 = (b/d)t\), and then \(y_0 - y = (a/d)t\).

Example: a museum sells adult tickets for 13 dollars and child tickets for 8 dollars, and one day takes in 341 dollars. How many of each could have been sold? Solve \(13x + 8y = 341\). Euclid gives \(\gcd(13, 8) = 1\) with \(13 \cdot (-3) + 8 \cdot 5 = 1\), so a particular solution is \(x_0 = -1023\), \(y_0 = 1705\), and the general solution is \(x = -1023 + 8t\), \(y = 1705 - 13t\). For both to be nonnegative we need \(t \ge 127.875\) and \(t \le 131.15\), so \(t = 128, 129, 130, 131\), giving \((x, y) = (1, 41), (9, 28), (17, 15), (25, 2)\). Four possible answers, and the shape of the general solution shows why: solutions differ by trading 8 adult tickets for 13 child tickets, which leaves the total unchanged.

A related classic is the coin problem. With coins worth \(a\) and \(b\) cents, \(\gcd(a, b) = 1\), which amounts can be paid exactly? Sylvester showed in 1884 that every amount greater than \(ab - a - b\) can be paid with nonnegative numbers of coins, and \(ab - a - b\) itself cannot. With 5-cent and 8-cent stamps the largest unpayable postage is \(40 - 5 - 8 = 27\) cents.

Linear congruences

A linear congruence \(ax \equiv b \pmod n\) is the same problem in disguise, since it says \(ax - ny = b\) for some integer \(y\). Solutions come in whole residue classes, so we count solutions modulo \(n\).

Theorem. Let \(d = \gcd(a, n)\). The congruence \(ax \equiv b \pmod n\) has a solution if and only if \(d \mid b\). In that case it has exactly \(d\) solutions modulo \(n\): if \(x_0\) is one, they are \[x_0,\ x_0 + \tfrac{n}{d},\ x_0 + 2\tfrac{n}{d},\ \ldots,\ x_0 + (d - 1)\tfrac{n}{d}.\]

Proof. Solvability is the Diophantine theorem. By that theorem the solutions are \(x = x_0 + (n/d)t\). Two of these, for \(t\) and \(t'\), are congruent modulo \(n\) exactly when \(n \mid (n/d)(t - t')\), that is, when \(d \mid t - t'\). So \(t = 0, 1, \ldots, d - 1\) give all the distinct classes.

The most important case is \(\gcd(a, n) = 1\): then there is exactly one solution, \(x \equiv a^{-1}b \pmod n\), where \(a^{-1}\) is the inverse from lesson 4. To solve \(7x \equiv 3 \pmod{40}\): the extended Euclidean algorithm gives \(7 \cdot 23 - 40 \cdot 4 = 1\), so \(7^{-1} \equiv 23\) and \(x \equiv 23 \cdot 3 = 69 \equiv 29 \pmod{40}\). Check: \(7 \cdot 29 = 203 = 5 \cdot 40 + 3\).

When \(d > 1\), divide everything by \(d\). To solve \(12x \equiv 18 \pmod{30}\): \(\gcd(12, 30) = 6\) divides 18, so there are six solutions. Dividing by 6 gives \(2x \equiv 3 \pmod 5\), whose solution is \(x \equiv 4 \pmod 5\). Modulo 30 the solutions are 4, 9, 14, 19, 24 and 29. On the other hand \(12x \equiv 15 \pmod{30}\) has no solution, since \(6 \nmid 15\): the left side is always a multiple of 6 modulo 30.

For small moduli a quicker trick often works: add multiples of the modulus to the right side until division is possible. For \(7x \equiv 3 \pmod{40}\): \(3 + 40 = 43\), \(3 + 80 = 83\), \(3 + 120 = 123\), \(3 + 160 = 163\), \(3 + 200 = 203 = 7 \cdot 29\). So \(x \equiv 29\).

Systems of congruences

The Sunzi Suanjing, a Chinese mathematical manual from the third to fifth century, asks: there are things whose number is unknown. Counted by threes, two remain; by fives, three remain; by sevens, two remain. How many things are there? In modern notation, find \(x\) with \[x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5, \qquad x \equiv 2 \pmod 7.\] The book gives the answer 23 and a method that works in general.

Theorem (Chinese remainder theorem). Let \(n_1, n_2, \ldots, n_k\) be pairwise coprime positive integers and \(N = n_1n_2\cdots n_k\). For any integers \(a_1, \ldots, a_k\), the system \[x \equiv a_1 \pmod{n_1}, \quad \ldots, \quad x \equiv a_k \pmod{n_k}\] has a solution, and any two solutions are congruent modulo \(N\).

Proof. Existence: let \(N_i = N/n_i\), the product of the other moduli. Since the moduli are pairwise coprime, \(\gcd(N_i, n_i) = 1\), so there is \(M_i\) with \(N_iM_i \equiv 1 \pmod{n_i}\). Set \[x = a_1N_1M_1 + a_2N_2M_2 + \cdots + a_kN_kM_k.\] Modulo \(n_i\), every term except the \(i\)-th is divisible by \(n_i\), because \(N_j\) contains the factor \(n_i\) for \(j \ne i\); and the \(i\)-th term is \(a_iN_iM_i \equiv a_i\). So \(x\) solves the system. Uniqueness: if \(x\) and \(x'\) both solve it, each \(n_i\) divides \(x - x'\). Pairwise coprime numbers that all divide a number have their product dividing it too (lesson 2, applied repeatedly), so \(N \mid x - x'\).

For Sunzi's problem: \(N = 105\), \(N_1 = 35\), \(N_2 = 21\), \(N_3 = 15\). Inverses: \(35 \equiv 2 \pmod 3\) has inverse 2; \(21 \equiv 1 \pmod 5\) has inverse 1; \(15 \equiv 1 \pmod 7\) has inverse 1. So \(x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}\). The things number 23, or 128, or 233, and so on.

In practice small systems are often easier to solve by substitution. From \(x \equiv 3 \pmod 5\), write \(x = 3 + 5s\). Then \(3 + 5s \equiv 2 \pmod 3\) gives \(2s \equiv 2\), so \(s \equiv 1 \pmod 3\), \(s = 1 + 3t\), and \(x = 8 + 15t\). Then \(8 + 15t \equiv 2 \pmod 7\) gives \(1 + t \equiv 2\), so \(t \equiv 1 \pmod 7\) and \(x = 23 + 105u\).

The theorem as a correspondence

The Chinese remainder theorem says that the map \[x \bmod N \ \longmapsto\ (x \bmod n_1, \ldots, x \bmod n_k)\] is a bijection from \(\mathbb{Z}_N\) to the set of \(k\)-tuples of residues: existence says it is onto, uniqueness says it is one to one. It also respects addition and multiplication, so it is an isomorphism of rings \(\mathbb{Z}_N \cong \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k}\). Calculations modulo \(N\) can be split into independent calculations modulo the factors and reassembled at the end.

The figure shows the bijection for \(N = 15\). Starting at 0 in the corner and moving one step down and one step right for each increase of \(n\), wrapping around the edges, the path visits every cell exactly once before returning to 0. If the moduli were not coprime, say 4 and 6, the path would close up early: after \(\operatorname{lcm}(4, 6) = 12\) steps it would be back at the start, having visited only 12 of the 24 cells. In particular \(x \equiv 1 \pmod 4\), \(x \equiv 2 \pmod 6\) has no solution, since the first congruence makes \(x\) odd and the second makes it even.

The correspondence also gives a multiplicative fact used in lesson 7: \(x\) is coprime to \(N\) exactly when each component \(x \bmod n_i\) is coprime to \(n_i\). So the number of units modulo \(N\) is the product of the numbers of units modulo each \(n_i\).

When the moduli are not coprime

Theorem. The system \(x \equiv a \pmod m\), \(x \equiv b \pmod n\) is solvable if and only if \(\gcd(m, n) \mid a - b\), and then the solution is unique modulo \(\operatorname{lcm}(m, n)\). Proof: \(x = a + ms\) solves the second congruence when \(ms \equiv b - a \pmod n\), which by the theorem on linear congruences is solvable exactly when \(\gcd(m, n) \mid b - a\), with \(s\) determined modulo \(n/\gcd(m, n)\), so \(x\) is determined modulo \(mn/\gcd(m, n)\).

Example: \(x \equiv 3 \pmod 4\), \(x \equiv 5 \pmod 6\). Here \(\gcd(4, 6) = 2\) divides \(5 - 3\), so there is a unique solution modulo 12. Trying \(3, 7, 11\): 11 works, since \(11 \equiv 5 \pmod 6\). Solution \(x \equiv 11 \pmod{12}\).

Applications

Computer algebra systems use the theorem to work with huge integers: to compute a large determinant or polynomial gcd exactly, compute it modulo many small primes, where arithmetic fits in a machine word, then reassemble the true answer. RSA implementations use it to decrypt about four times faster, working modulo the two prime factors \(p\) and \(q\) separately instead of modulo \(n = pq\). Astronomers and calendar makers used it to find when cycles of different lengths coincide: the Julian period of 7980 years, introduced by Joseph Scaliger in 1583, is \(28 \cdot 19 \cdot 15\), the product of the solar cycle, the lunar Metonic cycle and the Roman tax cycle, and each year in it is identified by its three cycle positions. Secret-sharing schemes by Mignotte and by Asmuth and Bloom distribute residues of a secret modulo different primes, so that enough residues together recover the secret by the Chinese remainder theorem.

Solving congruences by computer

The program solves linear congruences with any gcd, implements the Chinese remainder theorem for pairwise coprime moduli and the general version for arbitrary moduli, solves Sunzi's problem and the ticket problem, and finds the largest unpayable postage with 5- and 8-cent stamps.

import math

def solve_linear(a, b, n):
    """All solutions of a*x = b (mod n), as a sorted list of residues."""
    d = math.gcd(a, n)
    if b % d:
        return []
    a, b, m = a // d, b // d, n // d
    x0 = b * pow(a, -1, m) % m if m > 1 else 0
    return [x0 + k * m for k in range(d)]

print("7x = 3 (mod 40):", solve_linear(7, 3, 40))
print("12x = 18 (mod 30):", solve_linear(12, 18, 30))
print("12x = 15 (mod 30):", solve_linear(12, 15, 30))

def crt(residues, moduli):
    """General CRT; returns (x, lcm) or None if inconsistent."""
    x, m = 0, 1
    for a, n in zip(residues, moduli):
        g = math.gcd(m, n)
        if (a - x) % g:
            return None
        s = (a - x) // g * pow(m // g, -1, n // g) % (n // g) if n // g > 1 else 0
        x, m = x + m * s, m * n // g
        x %= m
    return x, m

print("Sunzi:", crt([2, 3, 2], [3, 5, 7]))
print("x=3 (4), x=5 (6):", crt([3, 5], [4, 6]), "  x=1 (4), x=2 (6):", crt([1, 2], [4, 6]))
print("big moduli:", crt([1, 2, 3], [10**9 + 7, 10**9 + 9, 998244353]))

tickets = [(x, (341 - 13 * x) // 8) for x in range(0, 341 // 13 + 1) if (341 - 13 * x) % 8 == 0]
print("13x + 8y = 341 with x, y >= 0:", tickets)

payable = {5 * i + 8 * j for i in range(20) for j in range(20)}
print("unpayable with 5 and 8:", [v for v in range(60) if v not in payable], " Sylvester:", 5 * 8 - 5 - 8)

7x = 3 (mod 40): [29]
12x = 18 (mod 30): [4, 9, 14, 19, 24, 29]
12x = 15 (mod 30): []
Sunzi: (23, 105)
x=3 (4), x=5 (6): (11, 12)   x=1 (4), x=2 (6): None
big moduli: (364869246337907870486762149, 998244368971909710889394239)
13x + 8y = 341 with x, y >= 0: [(1, 41), (9, 28), (17, 15), (25, 2)]
unpayable with 5 and 8: [1, 2, 3, 4, 6, 7, 9, 11, 12, 14, 17, 19, 22, 27]  Sylvester: 27

The general crt function merges one congruence at a time, which is exactly the substitution method above, and it detects inconsistent systems. The ticket problem has the four answers found by hand, and the unpayable postages with 5- and 8-cent stamps end at 27, as Sylvester's formula predicts.