Congruences and Linear Congruences

⚡ Key Takeaways

Congruence $a \equiv b \pmod{m}$ means $m \mid (a-b)$ — two integers leave the same remainder when divided by $m$ . A linear congruence $ax \equiv b \pmod m$ is solvable iff $\gcd(a,m) \mid b$ , in which case it has exactly $\gcd(a,m)$ solutions modulo $m$ . Used throughout number theory, cryptography, and computer arithmetic. Concept formalized by Gauss in Disquisitiones Arithmeticae (1801).

💡 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 $ax \equiv b \pmod m$ then reduces to a divisibility test ( $\gcd(a,m)\mid b$ ) plus the Extended Euclidean Algorithm, which simultaneously certifies solvability and produces the solution.

DefinitionCongruence Modulo m

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

1

\quad a \equiv b \pmod m \iff m \mid (a - b) \iff \exists k \in \mathbb{Z},\ a - b = km

Derivation hint: " $m$ divides $n$ " means $n = km$ for some integer $k$ ; apply directly to $n = a-b$ . Here $a, b \in \mathbb{Z}$ , $m \in \mathbb{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$ .

DefinitionResidue Class and the Ring

\mathbb{Z}/m\mathbb{Z}

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

2

\quad \bar a = \{\, x \in \mathbb{Z} : x \equiv a \pmod m \,\} = \{\, a + km : k \in \mathbb{Z}\,\}

Derivation hint: collect all integers congruent to $a$ ; by [1] they differ from $a$ by a multiple of $m$ . There are exactly $m$ distinct residue classes $\bar 0, \bar 1, \dots, \overline{m-1}$ , forming the quotient ring $\mathbb{Z}/m\mathbb{Z}$ under the well-defined operations $\bar a + \bar b = \overline{a+b}$ and $\bar a \cdot \bar b = \overline{ab}$ .

TheoremCongruence 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 \pmod m$ , then

3

\quad a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod m

Derivation hint: write $a-b = k_1 m$ , $c-d = k_2 m$ ; then $(a+c)-(b+d) = (k_1+k_2)m$ and $ac - bd = a(c-d) + d(a-b)$ , both multiples of $m$ .

DefinitionLinear Congruence

A linear congruence in the unknown $x$ is

4

\quad ax \equiv b \pmod m, \qquad a,b \in \mathbb{Z},\ m \in \mathbb{Z}_{>0}

Derivation hint: replace the equality in the linear equation $ax = 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).

TheoremSolvability and Solution Count

Let $d = \gcd(a,m)$ . The congruence $ax \equiv b \pmod m$ has a solution iff $d \mid b$ . When solvable, it has exactly $d$ incongruent solutions modulo $m$ . If $x_0$ is any one solution, all solutions are

5

\quad x \equiv x_0 + \frac{m}{d}\,t \pmod m, \qquad t = 0, 1, \dots, d-1

Derivation hint: divide $ax \equiv b$ through by $d$ to get $a'x \equiv b' \pmod{m'}$ with $\gcd(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.

ProofSolvability and Count

Step 1 — Reformulate as a Bézout problem. By [1], $ax \equiv b \pmod m$ means $m \mid (ax - b)$ , i.e. there exists $y$ with $ax - b = my$ , equivalently the linear Diophantine equation

ax - my = b.

Step 2 — Apply Bézout's identity. This Diophantine equation in $(x,y)$ is solvable iff $\gcd(a,m) \mid b$ . Set $d = \gcd(a,m)$ . If $d \nmid b$ there is no solution; this proves the solvability criterion.

Step 3 — Reduce to a coprime modulus. Assume $d \mid b$ and write $a = d a'$ , $b = d b'$ , $m = d m'$ with $\gcd(a', m') = 1$ . Dividing $ax \equiv b \pmod m$ by $d$ yields

a' x \equiv b' \pmod{m'}.

Step 4 — Unique solution mod $m'$ . Since $\gcd(a', m') = 1$ , $a'$ is invertible in $\mathbb{Z}/m'\mathbb{Z}$ (see [7] below). Multiplying by $(a')^{-1}$ gives a unique $x \equiv x_0 \pmod{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]. $\blacksquare$

∎

TheoremCancellation and Modular Inverse

If $\gcd(c,m)=1$ , then $ca \equiv cb \pmod m \implies a \equiv b \pmod m$ (cancellation is valid). More generally,

6

\quad ca \equiv cb \pmod m \implies a \equiv b \pmod{\tfrac{m}{\gcd(c,m)}}

Derivation hint: $m \mid c(a-b)$ ; remove the common factor $\gcd(c,m)$ from $c$ and $m$ , leaving $m/\gcd(c,m) \mid (a-b)$ since the reduced cofactor of $c$ is coprime to it. Consequently $a$ has a multiplicative inverse modulo $m$ iff $\gcd(a,m)=1$ , satisfying

7

\quad a\,a^{-1} \equiv 1 \pmod m, \quad \text{computable from } as + mt = 1 \text{ via the Extended Euclidean Algorithm}

Derivation hint: Bézout gives integers $s,t$ with $as+mt=1$ ; reducing mod $m$ gives $as \equiv 1$ , so $a^{-1} \equiv s$ .

Figure

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

Building Intuition

mathematician · 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.

ExampleA Congruence with a Unique Solution

Solve $7x \equiv 3 \pmod{10}$ .

Given: $a = 7,\ b = 3,\ m = 10$ . 1. Compute $d = \gcd(7,10) = 1$ . Since $1 \mid 3$ , a solution exists, and it is unique mod $10$ . 2. Find $7^{-1} \pmod{10}$ via Extended Euclid: $7 \cdot 3 = 21 \equiv 1 \pmod{10}$ , so $7^{-1} \equiv 3$ . 3. Multiply: $x \equiv 3 \cdot 3 = 9 \pmod{10}$ . 4. Check: $7 \cdot 9 = 63 = 60 + 3 \equiv 3 \pmod{10}$ . ✓

\boxed{x \equiv 9 \pmod{10}}

ExampleA Congruence with Several Solutions

Solve $6x \equiv 9 \pmod{15}$ .

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

\boxed{x \equiv 4,\ 9,\ 14 \pmod{15}}

⚠️ Common mistake

You cannot always cancel a common factor. From $6 \equiv 6 \pmod{4}$ ... harmless, but from $2 \cdot 3 \equiv 2 \cdot 1 \pmod 4$ you may not conclude $3 \equiv 1 \pmod 4$ — it happens to be false ( $3 \not\equiv 1 \pmod 4$ ). Cancellation of $c$ is legal only when $\gcd(c,m)=1$ ; otherwise the modulus must shrink to $m/\gcd(c,m)$ as in [6]. A second frequent error is treating $ax \equiv b \pmod m$ as if it always has a unique solution like a real equation; the solution count is $\gcd(a,m)$ , which may be $0$ (no solutions) or larger than $1$ .

Counterexample

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

connection

Congruences are the foundation of Modular Arithmetic and the ring structure of Quotient Rings: $\mathbb{Z}/m\mathbb{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 $\mathbb{Z}/m_1 \times \cdots \times \mathbb{Z}/m_k$ . The invertibility criterion $\gcd(a,m)=1$ identifies the Units in Modular Arithmetic, whose count is Euler's Totient Function $\varphi(m)$ , and whose order theory yields Fermat's Little Theorem and Euler's Theorem. The constructive engine throughout is the Extended Euclidean Algorithm.

🔬 Where this appears

⏳ History

- 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 \pmod p

in correspondence.

- 1736 — Euler publishes the first proof of Fermat's little theorem and later generalizes it via

\varphi(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

\mathbb{Z}

.

- 1801–1900s — Dirichlet, Dedekind, and Kronecker recast congruences as ideal-theoretic statements, birthing the ring

\mathbb{Z}/m\mathbb{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.

open-problem

While linear congruences are completely solved by the gcd criterion, their nonlinear cousins remain deep. Solving $ax \equiv b \pmod m$ is trivial, but solving the discrete logarithm $a^x \equiv b \pmod 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 $ax \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}$ ).

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also