1. The clock model
If it's 10 AM and you ask "what time will it be in four hours?", you don't say "14 o'clock" — you say "2 PM". The clock face only has the numbers $0$ through $11$, and once you pass $11$ you start again at $0$. The result of $10 + 4$ on the clock is $2$, even though the result on the number line is $14$.
That's all modular arithmetic is. Pick a fixed positive integer $n$ — call it the modulus. Take the integer line and wrap it into a circle of circumference $n$. Every integer lands on one of the $n$ positions $\{0, 1, 2, \ldots, n-1\}$. Integers that land in the same spot are treated as equal.
The picture above shows the wrap for $n = 12$. The integer $2$ on the line maps to position $2$ on the clock. So does $14$, and so does $26$, and so does $-10$ — they all land on the same dot, separated by full laps of $12$. The orange arc traces $10 + 4 \equiv 2 \pmod{12}$: starting at $10$, taking four steps clockwise, ending at $2$.
The clock picture isn't just a teaching prop — it's the literal geometric realization of $\mathbb{Z}/n\mathbb{Z}$. Adding by $n$ takes you exactly once around. The integers don't really "wrap"; they're projected onto a circle, and any two integers that project to the same point are, for modular purposes, the same.
2. Congruence and residue classes
For a positive integer $n$, integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod n$, iff $n \mid (a - b)$ — that is, their difference is an integer multiple of $n$.
Three equivalent ways to read $a \equiv b \pmod n$:
- $a$ and $b$ leave the same remainder when divided by $n$.
- $a - b$ is a multiple of $n$.
- $a$ and $b$ land on the same spot when you wrap the integers around a circle of size $n$.
Try it on $n = 12$: $14 \equiv 2 \pmod{12}$ because $14 - 2 = 12$, a multiple of $12$. Likewise $26 \equiv 2$ and $-10 \equiv 2$. The set of all integers congruent to $2$ mod $12$ is
$$ [2]_{12} \;=\; \{\ldots, -22, -10, 2, 14, 26, 38, \ldots\} \;=\; \{2 + 12k \mid k \in \mathbb{Z}\}. $$This set is called the residue class of $2$ modulo $12$. There are exactly $n$ such classes — one for each of $0, 1, 2, \ldots, n-1$. Together they partition every integer into $n$ buckets. The set of these classes, with the operations defined below, is denoted $\mathbb{Z}/n\mathbb{Z}$.
By convention, when someone writes "$a \bmod n$" they mean the unique representative of $[a]_n$ in the range $\{0, 1, \ldots, n-1\}$ — the "canonical" remainder. So $14 \bmod 12 = 2$, $-1 \bmod 12 = 11$, and $100 \bmod 7 = 2$ because $100 = 14 \cdot 7 + 2$.
Don't be thrown by $-1 \equiv 11 \pmod{12}$ — both representatives are correct; they refer to the same residue class. Pick whichever is more convenient. $-1$ is often the simpler one to compute with; $11$ is the conventional "canonical" form.
3. Operations that survive the wrap
Here is the fact that makes modular arithmetic worth its own name: addition, subtraction, and multiplication are well-defined on residue classes. That means if you replace any operand with another representative of its class, the answer stays in the same class. Formally, if $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$, then
$$ a + b \equiv a' + b' \pmod n, \quad a - b \equiv a' - b' \pmod n, \quad a \cdot b \equiv a' \cdot b' \pmod n. $$The practical consequence: you can reduce before you operate, not just after. Computing $437 \cdot 829 \bmod 11$? Reduce first: $437 \equiv 8$ and $829 \equiv 4$, so $437 \cdot 829 \equiv 8 \cdot 4 = 32 \equiv 10 \pmod{11}$. You never had to multiply the big numbers.
That's enormous computational leverage. The "last digit of $7^{1000}$" — a number with about 845 digits — is just $7^{1000} \bmod 10$, and you'll see in a moment how to do that without computing a single one of the actual $845$ digits.
A worked addition and a worked product
| Computation | Big-number version | Modular version |
|---|---|---|
| $(47 + 38) \bmod 9$ | $47 + 38 = 85; \; 85 = 9 \cdot 9 + 4$ | $47 \equiv 2,\; 38 \equiv 2; \; 2 + 2 = 4$ |
| $(47 \cdot 38) \bmod 9$ | $47 \cdot 38 = 1786; \; 1786 = 198 \cdot 9 + 4$ | $2 \cdot 2 = 4$ |
| $(-7) \bmod 12$ | $-7 + 12 = 5$ | $-7 \equiv 5 \pmod{12}$ |
What about division?
Division is where the analogy breaks. Over the integers — and again over the rationals — you can usually divide one number by another. Over $\mathbb{Z}/n\mathbb{Z}$, you sometimes can and sometimes can't, and the rule for "when" is the whole story of the next section.
From $2x \equiv 4 \pmod 6$ you might be tempted to "divide by 2" and conclude $x \equiv 2$. But $x = 5$ also works: $2 \cdot 5 = 10 \equiv 4 \pmod 6$. The cancellation rule that's automatic over the integers is conditional in $\mathbb{Z}/n\mathbb{Z}$.
4. When you can divide: multiplicative inverses
In ordinary arithmetic, "dividing by $a$" means "multiplying by $1/a$". The inverse $1/a$ exists for every nonzero real number. In modular arithmetic, the inverse of $a$ — the residue class $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod n$ — exists only sometimes, and exactly when one simple condition holds.
The integer $a$ has a multiplicative inverse modulo $n$ if and only if $\gcd(a, n) = 1$ — that is, $a$ and $n$ share no prime factors.
The intuition: if $a$ and $n$ share a common factor $d > 1$, then every multiple of $a$ also has $d$ as a factor of its residue mod $n$ — so $a \cdot x$ can never hit $1$, which has no factor of $d$. Conversely, if $\gcd(a, n) = 1$, the extended Euclidean algorithm produces integers $s, t$ with $sa + tn = 1$, and reducing mod $n$ gives $sa \equiv 1$ — so $s$ is the inverse.
Concrete examples
- $3 \bmod 7$: $3 \cdot 5 = 15 \equiv 1$, so $3^{-1} \equiv 5$.
- $5 \bmod 12$: $5 \cdot 5 = 25 \equiv 1$, so $5^{-1} \equiv 5$.
- $7 \bmod 10$: $7 \cdot 3 = 21 \equiv 1$, so $7^{-1} \equiv 3$.
- $4 \bmod 6$: $\gcd(4, 6) = 2$, no inverse exists.
- $6 \bmod 9$: $\gcd(6, 9) = 3$, no inverse exists.
- $10 \bmod 25$: $\gcd(10, 25) = 5$, no inverse exists.
The invertible residues form a special set called the group of units, written $(\mathbb{Z}/n\mathbb{Z})^\times$. Its size — the count of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$ — is the value of Euler's totient function $\varphi(n)$.
For $n = 12$: the integers in $\{1, \ldots, 12\}$ coprime to $12$ are $\{1, 5, 7, 11\}$, so $\varphi(12) = 4$.
If $p$ is prime, then $\gcd(a, p) = 1$ for every $a$ in $\{1, 2, \ldots, p-1\}$, so every nonzero residue class has an inverse. This makes $\mathbb{Z}/p\mathbb{Z}$ not just a ring but a field — the finite field $\mathbb{F}_p$. Inside it, division by any nonzero element works just like over the rationals.
5. Fermat's little theorem and Euler's theorem
One reason modular arithmetic is so powerful for big-exponent problems is that powers mod $n$ cycle, and the cycle length is captured by two clean theorems.
If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod p$.
Equivalently (and now for all integers $a$): $a^p \equiv a \pmod p$.
Canonical example: compute $3^{100} \bmod 5$. By Fermat, $3^4 \equiv 1 \pmod 5$ (since $5$ is prime and $\gcd(3, 5) = 1$). And $100 = 4 \cdot 25$, so
$$ 3^{100} \;=\; (3^4)^{25} \;\equiv\; 1^{25} \;=\; 1 \pmod 5. $$Without Fermat, you'd be staring at a 48-digit number. With Fermat, the answer is one line.
Fermat's theorem only applies when the modulus is prime. The generalization to any modulus — proved by Euler — replaces $p - 1$ with $\varphi(n)$:
If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod n$.
So for any modulus $n$, the powers of $a$ (when $a$ is coprime to $n$) cycle with period dividing $\varphi(n)$. To reduce an exponent: $a^k \bmod n$ can be replaced by $a^{k \bmod \varphi(n)} \bmod n$ — provided $\gcd(a, n) = 1$.
Example. $\varphi(10) = 4$ (the coprime residues are $\{1, 3, 7, 9\}$), so for any $a$ coprime to $10$, $a^4 \equiv 1 \pmod{10}$. The last digit of $7^{1000}$? Since $1000 = 4 \cdot 250$, we get $7^{1000} \equiv 1 \pmod{10}$. The last digit is $1$.
Fermat and Euler both require $\gcd(a, n) = 1$. Apply them to $0$ or to a value sharing a factor with $n$ and you'll get false statements like "$0^{p-1} \equiv 1$" — which is obviously wrong. The form $a^p \equiv a \pmod p$ does hold for all integers, but the inverse-style $a^{p-1} \equiv 1$ does not.
6. The Chinese Remainder Theorem
Two modular equations with coprime moduli can be combined into one. The Chinese Remainder Theorem (CRT) says exactly how — and that the combined answer is unique modulo the product.
Let $m$ and $n$ be coprime positive integers. For any integers $a$ and $b$, the system
$$ x \equiv a \pmod m, \qquad x \equiv b \pmod n $$has a unique solution modulo $mn$.
Worked example. Find an integer $x$ satisfying
$$ x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5. $$Since $\gcd(3, 5) = 1$, CRT promises a unique solution modulo $15$. Here's the search-and-check approach:
- List candidates satisfying the first congruence: $x \in \{2, 5, 8, 11, 14, \ldots\}$.
- Test each one against the second congruence ($x \equiv 3 \pmod 5$):
- $2 \bmod 5 = 2$ ✗
- $5 \bmod 5 = 0$ ✗
- $8 \bmod 5 = 3$ ✓
- So $x \equiv 8 \pmod{15}$ is the unique solution.
Check: $8 = 2 \cdot 3 + 2$, so $8 \equiv 2 \pmod 3$ ✓. And $8 = 1 \cdot 5 + 3$, so $8 \equiv 3 \pmod 5$ ✓.
For larger systems there's a formulaic approach using inverses ($M_i = N_i^{-1} \bmod n_i$ where $N_i = N/n_i$, then $x = \sum a_i N_i M_i \bmod N$), but the search method is fine for problems with small moduli and clarifies what CRT is really saying: two coprime-modulus constraints together are equivalent to a single constraint mod their product.
CRT lets you trade one hard problem mod $N$ for several easier problems modulo the prime-power factors of $N$. RSA implementations use it to speed up decryption by a factor of roughly four. And conceptually, it's the reason that asking "what is $x \bmod 15$?" is the same as asking "what is $x \bmod 3$ and $x \bmod 5$?" — two pieces of information that together pin $x$ down exactly.