Congruences and Linear Congruences

Congruence

a \equiv b (mod m)

means

m ∣ (a - b)

— two integers leave the same remainder when divided by

m

. A linear congruence

a x \equiv b (mod m)

is solvable iff

g cd (a, m) ∣ b

, in which case it has exactly

g cd (a, m)

solutions modulo

m

. Used throughout number theory, cryptography, and computer arithmetic. Concept formalized by Gauss in Disquisitiones Arithmeticae (1801).

A congruence is an equivalence relation on the integers that partitions $Z$ into residue classes according to remainder upon division by a fixed modulus $m$ . Linear congruences are the modular analogue of linear equations $a x = b$ , and their solution theory is the gateway to the Chinese Remainder Theorem, modular inverses, and public-key cryptography. The subject matters because it transforms infinitely many integer problems into finite arithmetic on the ring $Z / m Z$ , where computation is tractable. A surprising fact: a single linear congruence can have zero, one, or several incongruent solutions — unlike the real line, where $a x = b$ with $a \neq = 0$ always has exactly one — and the count is governed entirely by a greatest common divisor.

The Core Insight

Divisibility by $m$ is an equivalence relation that respects addition and multiplication. This lets us "compute modulo $m$ " inside a finite ring. Solving $a x \equiv b (mod m)$ then reduces to a divisibility test ( $g cd (a, m) ∣ b$ ) plus the Extended Euclidean Algorithm, which simultaneously certifies solvability and produces the solution.

Formal Statement

Congruence Modulo m

Let $m$ be a positive integer. Integers $a$ and $b$ are congruent modulo $m$ , written $a \equiv b (mod m)$ , if $m$ divides their difference:

a \equiv b (mod m) ⟺ m ∣ (a - b) ⟺ \exists k \in Z, a - b = k m

⟳"

m

divides

n

" means

n = k m

for some integer

k

; apply directly to

n = a - b

Here $a, b \in Z$ , $m \in Z_{> 0}$ is the modulus, and $k$ is the integer quotient of the difference. Equivalently, $a$ and $b$ have the same remainder under Euclidean division by $m$ .

Residue Class and the Ring $\mathbb{Z}/m\mathbb{Z}$

The residue class of $a$ modulo $m$ is the set

\overset{a}{ˉ} = {x \in Z : x \equiv a (mod m)} = {a + k m : k \in Z}

⟳collect all integers congruent to

a

; by [1] they differ from

a

by a multiple of

m

There are exactly $m$ distinct residue classes $\overset{ˉ}{0}, \overset{ˉ}{1}, \dots, \overline{m - 1}$ , forming the quotient ring $Z / m Z$ under the well-defined operations $\overset{a}{ˉ} + \overset{ˉ}{b} = \overline{a + b}$ and $\overset{a}{ˉ} \cdot \overset{ˉ}{b} = \overline{ab}$ .

Congruence is a Compatible Equivalence Relation

For fixed $m > 0$ , congruence mod $m$ is reflexive, symmetric, and transitive, and is preserved by addition, subtraction, and multiplication: if $a \equiv b$ and $c \equiv d (mod m)$ , then

a + c \equiv b + d, a - c \equiv b - d, a c \equiv b d (mod m)

⟳write

a - b = k_{1} m

c - d = k_{2} m

; then

(a + c) - (b + d) = (k_{1} + k_{2}) m

and

a c - b d = a (c - d) + d (a - b)

, both multiples of

m

Linear Congruence

A linear congruence in the unknown $x$ is

a x \equiv b (mod m), a, b \in Z, m \in Z_{> 0}

⟳replace the equality in the linear equation

a x = b

by congruence mod

m

A solution is any integer $x_{0}$ satisfying [4]; solutions come in entire residue classes, so we count solutions modulo $m$ (incongruent solutions).

Solvability and Solution Count

Let $d = g cd (a, m)$ . The congruence $a x \equiv b (mod m)$ has a solution iff $d ∣ b$ . When solvable, it has exactly $d$ incongruent solutions modulo $m$ . If $x_{0}$ is any one solution, all solutions are

x \equiv x_{0} + \frac{m}{d} t (mod m), t = 0, 1, \dots, d - 1

⟳divide

a x \equiv b

through by

d

to get

a^{'} x \equiv b^{'} (mod m^{'})

with

g cd (a^{'}, m^{'}) = 1

and

m^{'} = m / d

, which has a unique solution mod

m^{'}

; lift back to

m

to get

d

classes spaced

m / d

apart.

Why It Holds / Derivation

Solvability and Count

Step 1 — Reformulate as a Bézout problem. By [1],

a x \equiv b (mod m)

means

m ∣ (a x - b)

, i.e. there exists

y

with

a x - b = m y

, equivalently the linear Diophantine equation

a x - m y = b .

Step 2 — Apply Bézout's identity. This Diophantine equation in

(x, y)

is solvable iff

g cd (a, m) ∣ b

. Set

d = g cd (a, m)

. If

d ∤ b

there is no solution; this proves the solvability criterion. Step 3 — Reduce to a coprime modulus. Assume

d ∣ b

and write

a = d a^{'}

b = d b^{'}

m = d m^{'}

with

g cd (a^{'}, m^{'}) = 1

. Dividing

a x \equiv b (mod m)

d

yields

a^{'} x \equiv b^{'} (mod m^{'}) .

Step 4 — Unique solution mod $m^{'}$ . Since

g cd (a^{'}, m^{'}) = 1

a^{'}

is invertible in

Z / m^{'} Z

(see [7] below). Multiplying by

(a^{'})^{- 1}

gives a unique

x \equiv x_{0} (mod m^{'})

. Step 5 — Lift to $m$ and count. A residue class mod

m^{'}

splits into

m / m^{'} = d

residue classes mod

m

, namely

x_{0}, x_{0} + m^{'}, \dots, x_{0} + (d - 1) m^{'}

. These are exactly the

d

incongruent solutions in [5].

■

Cancellation and Modular Inverse

If $g cd (c, m) = 1$ , then $c a \equiv c b (mod m) ⟹ a \equiv b (mod m)$ (cancellation is valid). More generally,

c a \equiv c b (mod m) ⟹ a \equiv b (mod \frac{m}{g c d ( c , m )})

⟳

m ∣ c (a - b)

; remove the common factor

g cd (c, m)

from

c

and

m

, leaving

m / g cd (c, m) ∣ (a - b)

since the reduced cofactor of

c

is coprime to it.

Consequently $a$ has a multiplicative inverse modulo $m$ iff $g cd (a, m) = 1$ , satisfying

a a^{- 1} \equiv 1 (mod m), computable from a s + m t = 1 via the Extended Euclidean Algorithm

⟳Bézout gives integers

s, t

with

a s + m t = 1

; reducing mod

m

gives

a s \equiv 1

, so

a^{- 1} \equiv s

Residue classes mod 5 wrapping the number line onto a circle, and the orbit of multiplication by 2

Building Intuition

intuition Think of a clock with $m$ hours. Adding always wraps around, so $Z / m Z$ behaves like a finite circular ruler. Solving $a x \equiv b$ asks: "starting at $0$ and stepping by $a$ each time, do I ever land exactly on $b$ ?" The reachable points are precisely the multiples of $g cd (a, m)$ on the dial. If $b$ is one of them, you can land there in $g cd (a, m)$ symmetric ways; if it is not, you never can. This is why the gcd — not the magnitude of $a$ — controls everything.

Carl Friedrich Gauss | 1777–1855

Gauss introduced the notation $\equiv$ and the very word "congruence" in Disquisitiones Arithmeticae (1801), written when he was in his early twenties. By treating $\equiv$ like $=$ , he revealed that the integers carry a rich algebraic structure under divisibility, unifying scattered results of Fermat, Euler, and Lagrange. His systematic theory of congruences — including quadratic reciprocity, proved in the same work — founded modern number theory and made the modulus a first-class object of computation.

Worked Examples

A Congruence with a Unique Solution

Solve

7 x \equiv 3 (mod 10)

. Given:

a = 7, b = 3, m = 10

Compute $d = g cd (7, 10) = 1$ . Since $1 ∣ 3$ , a solution exists, and it is unique mod $10$ .
Find $7^{- 1} (mod 10)$ via Extended Euclid: $7 \cdot 3 = 21 \equiv 1 (mod 10)$ , so $7^{- 1} \equiv 3$ .
Multiply: $x \equiv 3 \cdot 3 = 9 (mod 10)$ .
Check: $7 \cdot 9 = 63 = 60 + 3 \equiv 3 (mod 10)$ . ✓

x \equiv 9 (mod 10)

A Congruence with Several Solutions

Solve

6 x \equiv 9 (mod 15)

. Given:

a = 6, b = 9, m = 15

$d = g cd (6, 15) = 3$ . Since $3 ∣ 9$ , the congruence is solvable with exactly $3$ incongruent solutions mod $15$ .
Divide through by $3$ : $2 x \equiv 3 (mod 5)$ .
Solve the reduced congruence: $2^{- 1} \equiv 3 (mod 5)$ (since $2 \cdot 3 = 6 \equiv 1$ ), so $x \equiv 3 \cdot 3 = 9 \equiv 4 (mod 5)$ . Take $x_{0} = 4$ .
Lift using [5] with $m / d = 5$ : $x \equiv 4, 4 + 5, 4 + 10 (mod 15)$ .
Check $x = 4$ : $6 \cdot 4 = 24 = 15 + 9 \equiv 9$ . ✓

x \equiv 4, 9, 14 (mod 15)

Common Misconceptions

You cannot always cancel a common factor. From

6 \equiv 6 (mod 4)

... harmless, but from

2 \cdot 3 \equiv 2 \cdot 1 (mod 4)

you may not conclude

3 \equiv 1 (mod 4)

— it happens to be false (

3 \neq \equiv 1 (mod 4)

). Cancellation of

c

is legal only when

g cd (c, m) = 1

; otherwise the modulus must shrink to

m / g cd (c, m)

as in [6]. A second frequent error is treating

a x \equiv b (mod m)

as if it always has a unique solution like a real equation; the solution count is

g cd (a, m)

, which may be

0

(no solutions) or larger than

1

Consider $2 x \equiv 3 (mod 4)$ . Here $d = g cd (2, 4) = 2$ but $2 ∤ 3$ , so no solution exists. Indeed $2 x$ is always even, hence $2 x mod 4 \in {0, 2}$ and can never equal $3$ . This shows the criterion $d ∣ b$ is genuinely necessary: an innocent-looking linear congruence can be outright unsolvable.

Connections

Congruences are the foundation of Modular Arithmetic and the ring structure of Quotient Rings: $Z / m Z$ is the prototypical quotient. Systems of simultaneous congruences with coprime moduli are solved by the Chinese Remainder Theorem, which reassembles the ring as a product $Z / m_{1} \times \dots \times Z / m_{k}$ . The invertibility criterion $g cd (a, m) = 1$ identifies the Units in Modular Arithmetic, whose count is Euler's Totient Function $φ (m)$ , and whose order theory yields Fermat's Little Theorem and Euler's Theorem. The constructive engine throughout is the Extended Euclidean Algorithm.

Real-World Applications

RSA cryptography — encryption and decryption are the modular exponentiations $c \equiv x^{e}$ and $x \equiv c^{d} (mod n)$ , with key generation solving $e d \equiv 1 (mod φ (n))$ , a linear congruence.
Hash tables and checksums — index $= key mod m$ ; ISBN-10, IBAN, and UPC use congruence-based check digits to detect transcription errors.
Pseudorandom number generators — linear congruential generators iterate $x_{n + 1} \equiv a x_{n} + c (mod m)$ .
Calendar algorithms — Zeller's congruence computes the day of week via arithmetic mod 7.
Diffie–Hellman key exchange — security rests on the discrete logarithm in $Z / p Z$ .
Error-correcting codes — Reed–Solomon and CRC codes compute remainders modulo a generator polynomial, the polynomial analogue of these congruences.
Cryptographic timing / clock synchronization — counters and rollover are managed with fixed-modulus arithmetic.

Historical Development

3rd c. CE — Sun Tzu's Sunzi Suanjing poses the first recorded simultaneous-congruence problem (counting an unknown by remainders), seeding the Chinese Remainder Theorem.
1247 — Qin Jiushao gives a general procedure (Dayan rule) for solving simultaneous congruences with non-coprime moduli.
1640 — Fermat states his little theorem $a^{p} \equiv a (mod p)$ in correspondence.
1736 — Euler publishes the first proof of Fermat's little theorem and later generalizes it via $φ (m)$ .
1801 — Gauss's Disquisitiones Arithmeticae introduces the $\equiv$ notation, the term "congruence," and the systematic theory of linear and quadratic congruences.
1832 — Gauss extends congruences to Gaussian integers, broadening the modulus concept beyond $Z$ .
1801–1900s — Dirichlet, Dedekind, and Kronecker recast congruences as ideal-theoretic statements, birthing the ring $Z / m Z$ and modern algebra.
1949 — D. H. Lehmer formalizes the linear congruential generator for computing.
1977 — Rivest, Shamir, and Adleman base RSA on linear and exponential congruences, turning the theory into critical infrastructure.

Subtleties & Limits

While linear congruences are completely solved by the gcd criterion, their nonlinear cousins remain deep. Solving $a x \equiv b (mod m)$ is trivial, but solving the discrete logarithm $a^{x} \equiv b (mod m)$ has no known efficient classical algorithm and underlies modern cryptography; Shor's quantum algorithm solves it in polynomial time, so its real-world hardness is conditional. Likewise, counting or finding solutions to general polynomial congruences mod composite $m$ is intimately tied to integer factorization. Even the distribution of solutions of $a x \equiv b$ as $a, b, m$ vary feeds open questions in analytic number theory about equidistribution of residues and the spacing of modular inverses (the Lehmer problem on $\sum$ of $x \cdot x^{- 1}$ ).

Congruences and Linear Congruences

The Core Insight

Formal Statement

Congruence Modulo m

Residue Class and the Ring $\mathbb{Z}/m\mathbb{Z}$

Congruence is a Compatible Equivalence Relation

Linear Congruence

Solvability and Solution Count

Why It Holds / Derivation

Solvability and Count

Cancellation and Modular Inverse

Residue classes mod 5 wrapping the number line onto a circle, and the orbit of multiplication by 2

Building Intuition

Carl Friedrich Gauss | 1777–1855

Worked Examples

A Congruence with a Unique Solution

A Congruence with Several Solutions

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads