Linear Congruences

Imagine a padlock whose dial only understands multiplication mod 12: to open it you must find a code x so that 7x \equiv 3 \pmod{12}. There's no dividing both sides by 7 the way you would with ordinary algebra — but the equation still has an answer, and finding it is the whole point of this page.

A linear congruence is the modular cousin of a linear equation:

ax \equiv b \pmod{n}.

We want every x (as a residue class mod n) that satisfies it. This is the same problem as a linear Diophantine equation wearing modular clothing, so exactly the same \gcd condition decides everything — whether the padlock has a code at all, and if so, how many codes work.

The coprime case: just invert

When \gcd(a, n) = 1, the inverse a^{-1} exists, and the congruence has exactly one solution modulo n — multiply both sides by it:

ax \equiv b \;\Longrightarrow\; a^{-1}ax \equiv a^{-1}b \;\Longrightarrow\; x \equiv a^{-1} b \pmod{n}.

That's the whole method: find the inverse of a, multiply it onto b, and reduce. No trial-and-error over every possible x from 0 to n - 1 needed, even when n is enormous.

Worked example: a single, fully-determined solution

Solve 3x \equiv 4 \pmod 7. First check \gcd(3, 7) = 1, so exactly one solution mod 7 is guaranteed. Next find 3^{-1} \pmod 7: since 3 \cdot 5 = 15 \equiv 1 \pmod 7, the inverse is 5. Multiply both sides of the congruence by it:

x \equiv 5 \cdot 4 = 20 \equiv 6 \pmod 7.

So x \equiv 6 is the answer — and only that one residue works modulo 7. Check it directly: 3 \cdot 6 = 18 = 14 + 4 \equiv 4 \pmod 7. It matches.

The general case

Let d = \gcd(a, n). Then ax \equiv b \pmod n:

When d \mid b, divide the whole congruence through by d to get a coprime one, \tfrac{a}{d}x \equiv \tfrac{b}{d} \pmod{n/d}. That smaller congruence has exactly one solution by the coprime case above — call it x_0. Then all d solutions modulo the original n are obtained by stepping x_0 forward by n/d each time:

x_0, \quad x_0 + \tfrac{n}{d}, \quad x_0 + 2\tfrac{n}{d}, \quad \dots, \quad x_0 + (d-1)\tfrac{n}{d} \pmod n.

Worked example: several solutions at once

Solve 4x \equiv 6 \pmod{10}. Here d = \gcd(4, 10) = 2, and 2 \mid 6, so there are exactly 2 solutions modulo 10. Divide everything by d = 2 to shrink it to a coprime congruence:

2x \equiv 3 \pmod 5.

Since 2^{-1} \equiv 3 \pmod 5 (because 2 \cdot 3 = 6 \equiv 1), this gives x \equiv 3 \cdot 3 = 9 \equiv 4 \pmod 5. That single answer, mod 5, blows back up into d = 2 answers mod the original 10, spaced n/d = 5 apart:

x \equiv 4 \pmod{10} \quad \text{and} \quad x \equiv 4 + 5 = 9 \pmod{10}.

Check both directly against the original congruence: 4 \cdot 4 = 16 \equiv 6 \pmod{10}, and 4 \cdot 9 = 36 \equiv 6 \pmod{10}. Both work — and no other residue mod 10 does.

With an ordinary equation ax = b over the real numbers (and a \ne 0), there is always exactly one solution: x = b/a. It is very tempting to carry that instinct straight over to ax \equiv b \pmod n — but a linear congruence does not have to behave that way at all.

Depending on \gcd(a, n), it can have exactly one solution (the coprime case), several solutions (as with 4x \equiv 6 \pmod{10} above, which has two — x \equiv 4 and x \equiv 9), or no solution at all. Try 6x \equiv 4 \pmod 9: here d = \gcd(6, 9) = 3, but 3 \nmid 4, so the theorem guarantees there is no solution whatsoever — not "hard to find," genuinely nonexistent. Every multiple of 6 mod 9 is a multiple of 3 (the shared factor), and 4 simply isn't one. Always check d \mid b before hunting for a solution — it tells you instantly whether there's anything to find.

Worked example: no solution

Confirm the claim above properly. For 6x \equiv 4 \pmod 9, compute d = \gcd(6, 9) = 3. Does 3 divide 4? No — 4 = 3 \cdot 1 + 1 leaves a remainder. By the theorem, that ends the search immediately: this congruence has zero solutions modulo 9. You could check all nine residues x = 0, 1, \dots, 8 by brute force and none would ever satisfy it — the multiples of 6 mod 9 cycle through only \{0, 6, 3\}, and 4 is never among them.

A general solver, in code

Putting the whole rule into one function makes the three outcomes concrete: no solution, one solution, or several. It reuses the modular-inverse routine from the previous page, applied to the coprime congruence left after dividing through by d:

function gcd(x: number, y: number): number { return y === 0 ? x : gcd(y, x % y); } function modInverse(a: number, n: number): number { let [oldR, r] = [a, n]; let [oldS, s] = [1, 0]; while (r !== 0) { const quotient = Math.floor(oldR / r); [oldR, r] = [r, oldR - quotient * r]; [oldS, s] = [s, oldS - quotient * s]; } return ((oldS % n) + n) % n; } function solveLinearCongruence(a: number, b: number, n: number): number[] { const d = gcd(a, n); if (b % d !== 0) return []; // no solution const aReduced = a / d; const bReduced = b / d; const nReduced = n / d; const x0 = (modInverse(aReduced, nReduced) * bReduced) % nReduced; const solutions: number[] = []; for (let k = 0; k < d; k++) solutions.push(x0 + k * nReduced); return solutions; } console.log(solveLinearCongruence(3, 4, 7)); // [6] console.log(solveLinearCongruence(4, 6, 10)); // [4, 9] console.log(solveLinearCongruence(6, 4, 9)); // [] — no solution

Three calls, three shapes of answer — a single fully-determined code, a short list of working codes, and an empty list meaning the padlock from the very first paragraph simply has no combination that opens it for that particular (a, b, n).

Why it matters

Linear congruences are the workhorses of modular problem-solving. They appear whenever you must "undo" a multiplication in a finite system — spacing out a repeating schedule, checking a digit in an ID number, or reversing a step in a cipher. Solving one is routine once you know the \gcd test; the real richness begins when several show up simultaneously, each with a different modulus.

Suppose a puzzle demands x \equiv 2 \pmod 3 and x \equiv 3 \pmod 5 at the same time. Solving one linear congruence is old news by now — but here are two, sharing a single unknown, with two different moduli. Do they even have a common solution? If so, how many?

This exact question was already being solved over a thousand years ago — the earliest known version appears in a 3rd-century Chinese text, posed as a puzzle about counting soldiers in unknown-sized rows. Today it has a name to match its origin: the Chinese Remainder Theorem. It turns out that whenever the moduli share no common factor, a system like this always has exactly one solution modulo the product of the moduli — and linear congruences, solved one at a time, are the building block that makes the whole trick work.