Congruences and Modular Arithmetic

What time is it, ten hours after 9 o'clock? Nobody computes $9+10=19$ and stops there. Everyone instinctively subtracts $12$ to get $7$ . This everyday act of "wrapping around" is arithmetic modulo $12$ . It is the seed of one of the most powerful ideas in number theory: congruence. Introduced by Carl Friedrich Gauss in 1801, the congruence notation replaces cumbersome divisibility statements. It offers a clean algebraic notation that behaves almost exactly like equality. The idea matters because so many questions about integers are really questions about remainders. Is a number divisible by 9? Look at its digit sum modulo 9. Does $x^2+1=0$ have a solution mod a prime $p$ ? That depends only on $p$ modulo $4$ . Whole swaths of number theory are conversations conducted entirely in the language of congruences. This includes divisibility tests, the structure of the integers modulo $n$ , and cryptographic algorithms like RSA. Congruences let us do algebra with remainders instead of with the integers themselves. They discard the irrelevant "bulk" of a number. Only what matters for a given question remains. The big picture is that congruence mod $n$ is an equivalence relation. It is compatible with addition, subtraction, and multiplication. This means the integers modulo $n$ do not just form a set of equivalence classes. They form a genuine algebraic system, later named $\mathbb{Z}/n\mathbb{Z}$ . In this system you can add, subtract, and multiply representatives. You get consistent, well-defined answers. This compatibility is not automatic for arbitrary equivalence relations. It is a theorem that must be proved. Proving it rigorously is the central goal of this article. This article builds the theory from the Division Algorithm up. It covers the formal definition of congruence and the proof that it is an equivalence relation. It also covers the three arithmetic laws — addition, subtraction, multiplication — that make modular arithmetic a working calculus. Division is deliberately excluded here. It requires care about invertibility and is the subject of Linear Congruences. What follows sets the stage for Residue Classes and Complete Residue Systems. It eventually leads to Fermat's Little Theorem.

Key takeaways

Congruence mod $n$ : $a \equiv b \pmod n$ means $n \mid (a-b)$ , a purely divisibility-based definition.
It is an equivalence relation: reflexive, symmetric, transitive — this partitions $\mathbb{Z}$ into $n$ residue classes.
Congruences add, subtract, and multiply just like equations: if $a\equiv b$ and $c \equiv d \pmod n$ , so do $a+c$ , $a-c$ , $ac$ .
A special case of multiplication gives exponentiation compatibility: $a\equiv b \pmod n \implies a^k \equiv b^k \pmod n$ .
Division is not automatic: $ac \equiv bc \pmod n$ does not imply $a \equiv b \pmod n$ unless $\gcd(c,n)=1$ .
These laws justify classical tests like "a number is divisible by 9 iff its digit sum is," proved rigorously below.
Key idea: congruence turns "same remainder on division by $n$ " into an algebraic equality that survives $+,-,\times$ .

Where this lives today

Modular arithmetic built on exactly these three laws (addition, subtraction, multiplication of congruences) underlies public-key cryptography: RSA encryption and decryption are congruence computations modulo a large composite number, and the correctness proof of RSA is a chain of congruence manipulations culminating in Euler's generalization of Fermat's Little Theorem. Check-digit schemes — ISBNs, credit card numbers (Luhn's algorithm), UPC barcodes — are direct applications of congruence arithmetic mod small numbers, catching single-digit and transposition errors by verifying that a weighted digit sum is congruent to a fixed value. In computer science, hash tables rely on congruence mod the table size to distribute keys, and modular arithmetic on fixed-width registers (mod $2^{32}$ or $2^{64}$ ) is literally how integer overflow behaves in most programming languages — a direct, if unintentional, application of the ring structure proved above. In abstract algebra, this article's theorem is the concrete special case $R = \mathbb{Z}$ of the general fact that congruence modulo an ideal is compatible with ring operations, which is how quotient rings are constructed. In signal processing and coding theory, cyclic redundancy checks (CRCs) treat data as coefficients of a polynomial and detect errors via congruence modulo a fixed generator polynomial, a direct descendant of the same additive/multiplicative compatibility proved here.

Ask the tutor: How do these three arithmetic laws combine to prove Fermat's Little Theorem?

n

Intuition

Picture the integers laid out on a number line, then imagine gluing the line into a circle of circumference $n$ by identifying every point with the point $n$ units to its right. Two integers become congruent mod $n$ exactly when this gluing sends them to the same spot on the circle. This is precisely the "clock arithmetic" picture: a clock with $n$ hours glues $0$ and $n$ together, and every integer lands on exactly one of the $n$ marks $0, 1, \dots, n-1$ . Concretely, fix $n = 5$ . The integers $\dots, -8, -3, 2, 7, 12, \dots$ all differ from each other by multiples of $5$ , so they are all congruent mod $5$ — they all sit at the same mark on a 5-hour clock, namely the mark labeled $2$ (since $2$ is the remainder of each of these numbers upon division by $5$ ). This clustering of $\mathbb{Z}$ into five families, one for each possible remainder $0,1,2,3,4$ , is the geometric content of congruence, and it is exactly why congruence deserves to be called an equivalence relation: it partitions the integers into disjoint classes. The second key intuition is algebraic robustness. Congruence is not just a static partition; it is compatible with the operations that make $\mathbb{Z}$ a ring. If two numbers are "the same" mod $n$ , then adding, subtracting, or multiplying them by anything congruent respects that sameness — the operations descend to the quotient. This is what makes modular arithmetic a genuine number system rather than a bookkeeping trick, and it is the theorem proved in detail below.

Figure

The five residue classes mod 5, wrapped onto a clock, and shown unrolled on the number line

+,-,\times

n \mid a - b

Worked examples

Example 1 — a digit-sum divisibility test, proved from the theorem, with an asymmetric number. Claim: $N = 4{,}186{,}935$ is divisible by $9$ if and only if the sum of its decimal digits is divisible by $9$ ; verify this for $N$ and find $N \bmod 9$ . Write $N$ in decimal as $N = \sum_{i=0}^{m} d_i \, 10^i$ where $d_i \in \{0, \dots, 9\}$ are the digits ( $d_0$ the units digit, etc.). Here $N = 4{,}186{,}935$ , so reading digits from the units place:

d_0 = 5,\ d_1=3,\ d_2=9,\ d_3=6,\ d_4=8,\ d_5=1,\ d_6=4.

Check: $4\cdot10^6+1\cdot10^5+8\cdot10^4+6\cdot10^3+9\cdot10^2+3\cdot10+5 = 4{,}186{,}935$ . Good. First, note $10 \equiv 1 \pmod 9$ , since $10 - 1 = 9$ . By part (6) of the theorem (powers), $10^i \equiv 1^i = 1 \pmod 9$ for every $i \ge 0$ (and trivially for $i=0$ by reflexivity). By part (5) applied repeatedly (multiplying $d_i \equiv d_i \pmod 9$ with $10^i \equiv 1 \pmod 9$ ), we get

d_i \cdot 10^i \equiv d_i \cdot 1 = d_i \pmod 9 \quad \text{for each } i.

Now apply part (4) (addition) repeatedly across all $i = 0, \dots, m$ to sum these congruences:

N = \sum_{i=0}^m d_i 10^i \equiv \sum_{i=0}^m d_i \pmod 9.

So $N$ is congruent mod $9$ to its digit sum $S = \sum d_i$ ; in particular $N \equiv 0 \pmod 9 \iff S \equiv 0 \pmod 9$ , which is exactly the classical rule. Now compute for our number: digit sum

S = 4+1+8+6+9+3+5 = 36.

Since $3+6=9$ and $9$ is divisible by $9$ , we get $S \equiv 0 \pmod 9$ , hence $36 \equiv 0 \pmod 9$ , hence by the congruence just derived, $N \equiv 0 \pmod 9$ . So $N = 4{,}186{,}935$ is divisible by $9$ . (Direct check: $4{,}186{,}935 / 9 = 465{,}215$ , an integer — confirms the claim.) Moreover, since $S = 36 \equiv 0 \pmod 9$ , we conclude $N \bmod 9 = 0$ , illustrating that the remainder of $N$ mod $9$ equals the remainder of its digit sum mod $9$ , not just a divisibility yes/no answer — a strictly stronger statement that follows from the same congruence $N \equiv S \pmod 9$ .

Example 2 — computing a large power's remainder using compatibility with multiplication and powers. Find the remainder when $7^{55}$ is divided by $13$ , without computing $7^{55}$ directly. We repeatedly use parts (5) and (6) to reduce the exponent's growth. First compute small powers of $7$ mod $13$ :

7^1 \equiv 7 \pmod{13}.

7^2 = 49 = 3\cdot 13 + 10 \equiv 10 \equiv -3 \pmod{13}.

So $7^2 \equiv -3 \pmod{13}$ . By part (6), raising both sides to the 4th power (i.e. applying powers to the congruence $7^2 \equiv -3$ ),

7^8 = (7^2)^4 \equiv (-3)^4 = 81 \pmod{13}.

Now reduce $81$ : $81 = 6\cdot 13 + 3$ , so $81 \equiv 3 \pmod{13}$ , giving

7^8 \equiv 3 \pmod{13}.

Next, write $55 = 8 \cdot 6 + 7$ , i.e. $7^{55} = (7^8)^6 \cdot 7^7 = (7^8)^6 \cdot 7^2 \cdot 7^5$ ; to keep this elementary and fully justified by parts (5)/(6) alone, we instead build up directly. By part (6), from $7^8 \equiv 3 \pmod{13}$ we get $(7^8)^6 \equiv 3^6 \pmod{13}$ . Compute $3^6$ stepwise mod $13$ using part (5) repeatedly:

3^2 = 9, \quad 3^3 = 27 \equiv 27-2\cdot13=1 \pmod{13}.

So $3^3 \equiv 1 \pmod{13}$ , and by part (6), $(3^3)^2 = 3^6 \equiv 1^2 = 1 \pmod{13}$ . Thus $(7^8)^6 \equiv 1 \pmod{13}$ , i.e. $7^{48} \equiv 1 \pmod{13}$ . Now $55 = 48 + 7$ , so $7^{55} = 7^{48}\cdot 7^{7}$ . By part (5) (multiplying the congruences $7^{48}\equiv 1$ and $7^7 \equiv 7^7$ ),

7^{55} \equiv 1 \cdot 7^7 = 7^7 \pmod{13}.

Finally compute $7^7 \bmod 13$ using the values already found: $7^2 \equiv -3$ , so by part (6) $7^4 = (7^2)^2 \equiv (-3)^2 = 9 \pmod{13}$ , and $7^6 = 7^4\cdot 7^2 \equiv 9 \cdot(-3) = -27 \equiv -27+3\cdot13 = 12 \equiv -1 \pmod{13}$ (using part (5)). Then

7^7 = 7^6 \cdot 7 \equiv (-1)\cdot 7 = -7 \equiv 6 \pmod{13}

(using part (5) again, and $-7 + 13 = 6$ ). Therefore $7^{55} \equiv 6 \pmod{13}$ ; the remainder of $7^{55}$ upon division by $13$ is $\boxed{6}$ . Every step used only reflexivity, and parts (4)–(6) of the theorem — never a direct evaluation of $7^{55}$ itself, which has 47 digits.

\gcd(c,n)=1

Scope, edge cases & common traps

Situation	What holds	What can fail
$n=1$	Every integer is congruent to every other integer mod $1$ (only one residue class)	Congruence mod 1 carries no information
Negative $a,b$	Definition and all proofs work unchanged ( $n \mid a-b$ makes sense for any integers)	Forgetting negative remainders exist; always use $0 \le r < n$ from the Division Algorithm
Adding/subtracting congruences	Always valid (Theorem parts 4)	None — fully general
Multiplying congruences	Always valid (Theorem part 5)	None — fully general
Cancelling a common factor $c$ from $ac\equiv bc$	Valid only if $\gcd(c,n)=1$	False in general — see counterexample above
Dividing both sides and the modulus by $d=\gcd(c,n)$	$ac\equiv bc \pmod n \Rightarrow a \equiv b \pmod{n/d}$	Easy to misstate as "mod $n$ " instead of "mod $n/d$ "

The mathematician behind it

Origins · 1 minCarl Friedrich Gauss and how this was discovered

Carl Friedrich Gauss

1777–1855 · Germany, Duchy of Brunswick and Kingdom of Hanover

Gauss introduced the congruence notation $a \equiv b \pmod n$ in his 1801 treatise Disquisitiones Arithmeticae, written when he was in his early twenties. He designed the notation deliberately to evoke ordinary equality, precisely because — as the theorem above shows — congruence really does obey addition, subtraction, and multiplication laws parallel to those of equality. Gauss used this apparatus to develop the theory of quadratic residues, prove the law of quadratic reciprocity, and lay the groundwork for what would become modern algebraic number theory. Beyond number theory, Gauss made foundational contributions to geometry, statistics (the normal distribution and least squares), astronomy (predicting the orbit of the dwarf planet Ceres), and magnetism; the CGS unit of magnetic flux density, the gauss, is named for him.

History

- 1777 — Carl Friedrich Gauss is born in Braunschweig (Brunswick).

- 1796 — At age 19, Gauss proves the constructibility of the regular 17-gon by straightedge and compass.

- 1801 — Gauss publishes Disquisitiones Arithmeticae, introducing the congruence notation

\equiv \pmod n

and systematically developing its arithmetic.

- 1801 — Gauss also uses congruence-based methods to recompute and successfully predict the reappearance of Ceres.

- 1855 — Gauss dies in Göttingen, having shaped number theory, geometry, and statistics for the following two centuries.

What exactly does

a \equiv b \pmod n

mean, in the simplest terms?

It means $n$ divides the difference $a - b$ exactly, with no remainder. Equivalently, and more intuitively, it means $a$ and $b$ leave the same remainder when you divide each of them by $n$ — this equivalence is proved as part (0) of the theorem above using the Division Algorithm. For example, $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$ is divisible by $12$ , and indeed both $17$ and $5$ leave remainder $5$ when divided by $12$ . This is the same idea as clock arithmetic: 17 o'clock and 5 o'clock are "the same time" on a 12-hour clock.

Is congruence the same thing as equality?

No, but it behaves remarkably like equality for addition, subtraction, and multiplication, which is exactly why Gauss chose a notation resembling " $=$ ". The crucial difference is that congruence forgets information: infinitely many integers (e.g. all of $\dots,-19,-7,5,17,29,\dots$ ) are congruent to each other mod $12$ , whereas equality distinguishes every integer from every other. Congruence is coarser than equality — it is equality "up to multiples of $n$ ." Division is where the analogy with equality breaks most sharply: you cannot always cancel a common factor from a congruence, as the counterexample above demonstrates.

Can I always add, subtract, or multiply congruences freely, mixing different ones?

Yes — that is precisely the content of parts (4) and (5) of the theorem. If $a \equiv b \pmod n$ and $c \equiv d \pmod n$ (same modulus $n$ in both), then you may freely form $a+c \equiv b+d$ , $a - c\equiv b-d$ , and $ac \equiv bd$ , all still modulo $n$ . You may also raise both sides of a single congruence to any positive integer power. What you may not do in general is divide both sides by a common factor, or mix two congruences with different moduli into a single new congruence without extra justification (such as the Chinese Remainder Theorem, a separate result).

Why is congruence called an "equivalence relation," and why does that matter?

An equivalence relation is any relation satisfying reflexivity, symmetry, and transitivity, and the article's theorem proves congruence mod $n$ satisfies all three. This matters because equivalence relations automatically partition their underlying set into disjoint classes — no two distinct classes overlap, and every element belongs to exactly one class. For congruence mod $n$ , this partition has exactly $n$ classes, corresponding to remainders $0,1,\dots,n-1$ ; this partition is called the set of Residue Classes and Complete Residue Systems, the natural next topic once congruence itself is understood.

Does congruence work the same way for negative integers?

Yes, completely unchanged. The definition $n \mid (a-b)$ makes sense for any integers $a, b$ , positive, negative, or zero, and every proof above used only this definition together with the Division Algorithm, which also holds for negative $a$ (the remainder $r$ is still required to satisfy $0 \le r < n$ ). For instance, $-8 \equiv 2 \pmod 5$ because $-8 - 2 = -10$ is divisible by $5$ , and indeed $-8 = (-2)(5) + 2$ shows $-8$ has remainder $2$ upon division by $5$ , matching the remainder of $2$ itself.

How does this connect to Fermat's Little Theorem?

Fermat's Little Theorem states that if $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ . Its proof relies entirely on the arithmetic laws established here: multiplying congruences together, cancelling under the coprimality condition $\gcd(a,p)=1$ (which is guaranteed when $p \nmid a$ since $p$ is prime), and using the "powers" compatibility (part 6 above) to manipulate exponents. In other words, this article's theorem is the toolbox; Fermat's Little Theorem is one of its first spectacular applications, developed once residue systems are in place.

What's the difference between "mod" as in

a \bmod n

(an operation returning a number) and "

\pmod n

" as in a congruence statement?

These are related but distinct uses. The expression $a \bmod n$ (no parentheses, used as an operator) denotes the specific remainder $r$ with $0 \le r < n$ produced by the Division Algorithm applied to $a$ and $n$ — it is a single integer. The notation " $a \equiv b \pmod n$ " (with parentheses around "mod $n$ ") is a relation between two integers $a$ and $b$ , asserting $n \mid (a-b)$ ; it is a true-or-false statement, not a number. Part (0) of the theorem links them: $a \equiv b \pmod n$ if and only if $a \bmod n = b \bmod n$ .