1. Divisibility
For integers $a, b$, we say $a$ divides $b$ — written $a \mid b$ — if there is an integer $k$ such that $b = ak$. Equivalently, $b/a$ is an integer.
Read $a \mid b$ as "$a$ divides $b$" or "$b$ is a multiple of $a$." Don't confuse it with the fraction $a/b$ — the vertical bar is a relation (true or false), not a number.
A handful of facts are used so often that they may as well be reflexes. For any integers $a, b, c$:
- $a \mid a$ (reflexive) and $a \mid 0$ (every integer divides zero).
- If $a \mid b$ and $b \mid c$, then $a \mid c$ (transitive).
- If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y$. (Divisors of $b$ and $c$ are divisors of every linear combination of $b$ and $c$.)
- If $a \mid b$ and $b \neq 0$, then $|a| \leq |b|$.
That third bullet — divisors survive linear combinations — is the workhorse of every proof in this page. Tag it mentally.
2. The division algorithm
"Algorithm" is a misnomer; it's a theorem, and the most important fact about $\mathbb{Z}$ on this page.
For any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that
$$ a = bq + r, \qquad 0 \leq r < b. $$Two things to notice. First, the remainder is always non-negative and strictly less than $b$ — even when $a$ is negative. Second, $q$ and $r$ are unique: given the constraint on $r$, there is exactly one way to split $a$ into a multiple of $b$ plus a leftover.
A quick example. Take $a = 17$, $b = 5$. Then $17 = 5 \cdot 3 + 2$, so $q = 3$, $r = 2$. For $a = -17$, $b = 5$, you might be tempted to write $-17 = 5 \cdot (-3) + (-2)$, but $r$ must be non-negative. The correct split is $-17 = 5 \cdot (-4) + 3$.
Many programming languages' % operator can return a negative remainder when the dividend is negative (C, Java do this; Python doesn't). The mathematical remainder defined here is always in $[0, b)$. When in doubt, add $b$ until $r$ lands in the right range.
Why does this matter? Because every other result in the page — gcd, the Euclidean algorithm, Bézout, prime factorization, modular arithmetic itself — is downstream of this single guarantee that integers split cleanly.
3. GCD and LCM
For integers $a, b$ (not both zero), $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$.
For positive integers $a, b$, $\mathrm{lcm}(a, b)$ is the smallest positive integer that is a multiple of both $a$ and $b$.
These two quantities are joined at the hip by the identity
$$ \gcd(a, b) \cdot \mathrm{lcm}(a, b) = |ab|. $$So once you have one, the other is free. Compute $\gcd(12, 18) = 6$, and $\mathrm{lcm}(12, 18) = 12 \cdot 18 / 6 = 36$. No second algorithm needed.
You can compute either by factoring both numbers into primes and reading off the relevant exponents — but factoring is hard for large numbers, and the next section gives a much faster route to the gcd that doesn't need to factor anything.
4. The Euclidean algorithm
The Euclidean algorithm — already in Elements Book VII, around 300 BCE — computes $\gcd(a, b)$ in a number of steps roughly proportional to the number of digits, not to the size of $a$ or $b$. It's astonishingly fast, and the idea is one move:
$\gcd(a, b) = \gcd(b, r)$, where $r$ is the remainder when $a$ is divided by $b$.
Write $a = bq + r$ with $0 \leq r < b$. Any common divisor of $a$ and $b$ divides $a - bq = r$, so it's a common divisor of $b$ and $r$. Conversely, any common divisor of $b$ and $r$ divides $bq + r = a$, so it's a common divisor of $a$ and $b$. The two pairs $(a, b)$ and $(b, r)$ have exactly the same set of common divisors — and therefore the same greatest one. ∎
Apply the move repeatedly: the remainders shrink (each is strictly less than the previous divisor), the sequence terminates when the remainder hits $0$, and the last non-zero remainder is $\gcd(a, b)$.
Worked example: $\gcd(252, 198)$
Plug into the recipe:
| Step | Division | New pair |
|---|---|---|
| 1 | 252 = 198 · 1 + 54 | (198, 54) |
| 2 | 198 = 54 · 3 + 36 | (54, 36) |
| 3 | 54 = 36 · 1 + 18 | (36, 18) |
| 4 | 36 = 18 · 2 + 0 | stop |
The last non-zero remainder is $18$, so $\gcd(252, 198) = 18$.
Check by factoring: $252 = 2^2 \cdot 3^2 \cdot 7$ and $198 = 2 \cdot 3^2 \cdot 11$, so the shared part is $2 \cdot 3^2 = 18$. ✓ Notice how Euclid's procedure never even looked at the primes — it's pure division.
Each step at least halves the smaller number every two iterations (a fact you can prove with a little case analysis). So the number of steps is bounded by roughly $2 \log_2(\min(a, b))$ — logarithmic in the input. The worst case turns out to be consecutive Fibonacci numbers, which is a beautiful and unexpected connection.
5. The extended Euclidean algorithm and Bézout
The Euclidean algorithm gives you the gcd. The extended version gives you something much more: an explicit way to write the gcd as an integer combination of $a$ and $b$.
For any integers $a, b$ (not both zero), there exist integers $x, y$ such that
$$ \gcd(a, b) = ax + by. $$The pair $(x, y)$ is called Bézout coefficients. It's never unique — if one pair works, infinitely many do — but it always exists.
The idea is to run the Euclidean algorithm forward, then unwind it backward, substituting each remainder in terms of the previous two numbers.
Worked example: Bézout for $\gcd(252, 198) = 18$
Take the equations from the previous section and rearrange each so the remainder is alone on the left:
$$ \begin{aligned} 54 &= 252 - 198 \cdot 1 \\ 36 &= 198 - 54 \cdot 3 \\ 18 &= 54 - 36 \cdot 1 \end{aligned} $$Now back-substitute, starting from the bottom equation, replacing $36$ then $54$ until everything is in terms of $252$ and $198$:
$$ \begin{aligned} 18 &= 54 - 36 \cdot 1 \\ &= 54 - (198 - 54 \cdot 3) \cdot 1 \\ &= 54 \cdot 4 - 198 \cdot 1 \\ &= (252 - 198) \cdot 4 - 198 \\ &= 252 \cdot 4 - 198 \cdot 5. \end{aligned} $$So $\gcd(252, 198) = 18 = 252 \cdot 4 + 198 \cdot (-5)$. The Bézout coefficients are $x = 4$, $y = -5$. Check: $252 \cdot 4 = 1008$, $198 \cdot 5 = 990$, and $1008 - 990 = 18$. ✓
Bézout's identity is what unlocks the rest of elementary number theory. It's the reason inverses exist modulo $n$ when $\gcd(a, n) = 1$ (find $x$ with $ax + ny = 1$, then $x \equiv a^{-1} \pmod n$). It's the reason linear Diophantine equations $ax + by = c$ have integer solutions exactly when $\gcd(a, b) \mid c$. And it's a key lemma on the way to the Fundamental Theorem of Arithmetic.
A tabular form of the extended algorithm
Maintain three columns — the running remainder $r$ and Bézout coefficients $x, y$ — so that at every row, $r = a x + b y$. Start with two seed rows: $(a, 1, 0)$ and $(b, 0, 1)$. At each step compute the quotient $q$ of the previous two remainders, then subtract $q$ times the lower row from the upper to produce the next row.
For $\gcd(252, 198)$:
| r | x | y | note |
|---|---|---|---|
| 252 | 1 | 0 | seed: 252 = 252·1 + 198·0 |
| 198 | 0 | 1 | seed: 198 = 252·0 + 198·1 |
| 54 | 1 | −1 | q = 1; (252) − 1·(198) |
| 36 | −3 | 4 | q = 3; (198) − 3·(54) |
| 18 | 4 | −5 | q = 1; (54) − 1·(36) |
| 0 | — | — | stop; previous row is the answer |
The last non-zero row reads $18 = 252 \cdot 4 + 198 \cdot (-5)$ — the same Bézout pair we got by hand.
6. Coprimality and Euclid's lemma
Integers $a$ and $b$ are coprime if $\gcd(a, b) = 1$. Equivalently, by Bézout, there exist integers $x, y$ with $ax + by = 1$.
Coprimality is sharper than "share no obvious factor" — it's the precise statement that $a$ and $b$ have no prime in common. For example, $9$ and $14$ are coprime ($3^2$ versus $2 \cdot 7$), even though neither is prime.
The following lemma is small, elegant, and indispensable.
If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
Suppose $p \mid ab$ and $p \nmid a$. We must show $p \mid b$. Because $p$ is prime and $p \nmid a$, the only positive divisors $p$ shares with $a$ are factors of $1$ — so $\gcd(p, a) = 1$. By Bézout there exist integers $x, y$ with $px + ay = 1$. Multiply by $b$:
$$ pbx + aby = b. $$The first term $pbx$ is divisible by $p$. The second term $aby = (ab) y$ is divisible by $p$ because $p \mid ab$ by assumption. So $p$ divides the right-hand side $b$. ∎
Euclid's lemma is what makes primes behave like the atoms of multiplication: a prime cannot be "split" between two factors of a product without picking a side. Without this, the next theorem would be false.
The lemma extends inductively: if a prime $p$ divides a product $a_1 a_2 \cdots a_n$, then $p$ divides at least one of the $a_i$.
7. The Fundamental Theorem of Arithmetic
Every integer $n > 1$ can be written as a product of primes
$$ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} $$and this factorization is unique up to the order in which the primes are written.
"Existence" is the easy half. "Uniqueness" is the surprising half — and the half that demands Euclid's lemma to prove. Here is the structure of the argument.
Strong induction on $n$. If $n = 2$, $n$ is itself prime — done. For $n > 2$, either $n$ is prime (done), or $n = ab$ with $1 < a, b < n$. By induction $a$ and $b$ are each products of primes; concatenate the lists to get one for $n$. ∎
Suppose $n$ has two prime factorizations:
$$ n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s. $$The prime $p_1$ divides the left side, hence divides the right. By Euclid's lemma (extended to a product of many factors), $p_1$ divides some $q_j$. But $q_j$ is itself prime, so its only divisors are $1$ and $q_j$ — and since $p_1 > 1$, we get $p_1 = q_j$. Cancel both sides by $p_1 = q_j$ and repeat. After $r$ rounds the left side is empty; the right must be too, so $r = s$ and the lists are the same multiset of primes. ∎
It feels obvious because you've been doing it since middle school — but it's a real theorem. There are number systems where unique factorization fails. In $\mathbb{Z}[\sqrt{-5}]$, $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$, with all four factors "prime" in that ring. Uniqueness in $\mathbb{Z}$ is a feature of the integers, not a tautology. (For more, see algebraic number theory.)
8. Infinitude of primes — Euclid's proof
One of the oldest non-trivial theorems in mathematics, and still arguably the most beautiful proof in elementary number theory. Euclid's Elements, Book IX, Proposition 20.
There are infinitely many prime numbers.
Suppose, for contradiction, that there are only finitely many primes. List them all:
$$ p_1, p_2, \ldots, p_n. $$Now form the integer
$$ N = p_1 p_2 \cdots p_n + 1. $$Since $N > 1$, by the Fundamental Theorem of Arithmetic, $N$ has at least one prime factor — call it $p$. By assumption $p$ is one of the listed primes, so $p = p_i$ for some $i$. Then $p_i$ divides $N$ and $p_i$ divides the product $p_1 p_2 \cdots p_n$, so $p_i$ divides their difference:
$$ p_i \mid (N - p_1 p_2 \cdots p_n) = 1. $$But no prime divides $1$. Contradiction. So our finite list was incomplete; there must be infinitely many primes. ∎
The proof does not say that $N = p_1 p_2 \cdots p_n + 1$ is itself prime. It says $N$ has some prime factor not on the list. For example, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ — composite, but its prime factors $59$ and $509$ aren't in the starting list. The contradiction still goes through.
Once you accept there are infinitely many primes, the natural next question is how they are distributed. That belongs to analytic number theory (the Prime Number Theorem: roughly $\pi(x) \sim x / \ln x$). Here we just note that, despite their infinitude, primes thin out — and many of the most stubborn open questions in mathematics are about exactly how they thin out.
9. A small zoo: Mersenne, Fermat, twin primes
Once you start hunting primes, you start naming families. A few keep showing up.
Mersenne primes
A Mersenne number is one of the form $M_n = 2^n - 1$. When $M_n$ happens to be prime, it's a Mersenne prime. The first few: $M_2 = 3$, $M_3 = 7$, $M_5 = 31$, $M_7 = 127$. They appear in the Euclid–Euler theorem connecting even perfect numbers to Mersenne primes, and modern record-largest-prime searches almost always find Mersenne primes (because the form admits a very fast primality test). As of writing, fewer than sixty are known — and it's not known whether infinitely many exist.
Fermat primes
Fermat numbers are $F_n = 2^{2^n} + 1$. Fermat conjectured all of them were prime; the first five — $3, 5, 17, 257, 65537$ — are. Euler then found $F_5 = 4{,}294{,}967{,}297 = 641 \cdot 6{,}700{,}417$. Embarrassing. In fact, no Fermat prime past $F_4$ has ever been found, and it's not known whether there are any.
Twin primes
A twin prime pair is two primes that differ by $2$: $(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), \ldots$. The twin prime conjecture asserts there are infinitely many such pairs. It remains famously unproven. Yitang Zhang's 2013 breakthrough showed there are infinitely many prime pairs separated by at most some finite gap (initially 70 million; tightened to 246 in subsequent work) — a tantalizing partial result.
These three teasers are all about how often primes of certain shapes occur. Elementary number theory gives the language and the easy answers; the hard answers live in analytic and algebraic number theory, and many remain out of reach.
10. Common pitfalls
$a \mid b$ is a relation (true or false). $a / b$ is a number. So $3 \mid 12$ is "true," not "$4$." Watch the direction too: $a \mid b$ means $a$ goes into $b$, not the other way around.
The division algorithm fixes $0 \leq r < b$. For $a = -17, b = 5$, the correct $(q, r)$ is $(-4, 3)$, not $(-3, -2)$. Programming languages disagree on this — the math doesn't.
$1$ is not prime, by convention — and the convention exists precisely so that the Fundamental Theorem of Arithmetic's uniqueness clause works. If $1$ counted, you could pad any factorization with arbitrarily many $1$s and uniqueness would die.
"$N = p_1 \cdots p_n + 1$ is prime" is the wrong takeaway. The proof says $N$ has some prime factor not in the original list — $N$ itself may well be composite. Confusing this leads to false claims (the smallest counterexample, again: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$ is not prime).
Euclid's lemma is sharp: it needs $p$ to be prime. The composite version is false. $6 \mid 4 \cdot 9 = 36$, but $6 \nmid 4$ and $6 \nmid 9$. Without primality, "divides a product" doesn't force "divides a factor."
11. Worked examples
Try each yourself before opening the solution. The goal is to compare your steps to the canonical recipe — not the final number alone.
Example 1 · Apply the division algorithm to $a = -47$, $b = 6$
We need $q, r$ with $-47 = 6q + r$ and $0 \leq r < 6$. Try $q = -8$: then $6q = -48$, so $r = -47 - (-48) = 1$. Check: $0 \leq 1 < 6$ ✓ and $-47 = 6(-8) + 1$ ✓. So $q = -8$, $r = 1$.
The "naive" answer $q = -7, r = -5$ is wrong because the remainder must be non-negative.
Example 2 · Compute $\gcd(1071, 462)$ by the Euclidean algorithm
Run the chain of divisions:
| 1071 = 462 · 2 + 147 |
| 462 = 147 · 3 + 21 |
| 147 = 21 · 7 + 0 |
Last non-zero remainder is $21$, so $\gcd(1071, 462) = 21$.
Example 3 · Find Bézout coefficients for $\gcd(1071, 462) = 21$
Rearrange the two key divisions:
$$ \begin{aligned} 147 &= 1071 - 462 \cdot 2 \\ 21 &= 462 - 147 \cdot 3 \end{aligned} $$Back-substitute:
$$ \begin{aligned} 21 &= 462 - 147 \cdot 3 \\ &= 462 - (1071 - 462 \cdot 2) \cdot 3 \\ &= 462 \cdot 7 - 1071 \cdot 3 \\ &= 1071 \cdot (-3) + 462 \cdot 7. \end{aligned} $$So $21 = 1071 \cdot (-3) + 462 \cdot 7$. Check: $-3213 + 3234 = 21$ ✓.
Example 4 · Use Euclid's lemma to show: if $p$ prime and $p \mid a^2$, then $p \mid a$
$a^2 = a \cdot a$. By Euclid's lemma, $p \mid a \cdot a$ implies $p \mid a$ or $p \mid a$. Either way, $p \mid a$. ∎
This single-line lemma is the engine behind the classical proof that $\sqrt{2}$ is irrational.
Example 5 · Find the prime factorization of $360$ and read off $d(360)$
Pull out primes from smallest to largest:
$$ 360 = 2 \cdot 180 = 2^2 \cdot 90 = 2^3 \cdot 45 = 2^3 \cdot 3^2 \cdot 5. $$The exponents are $(3, 2, 1)$. The number of positive divisors is $(3+1)(2+1)(1+1) = 24$. The FTA guarantees this is the only factorization of $360$ into primes (up to order).
Example 6 · Why does Euclid's $N + 1$ trick fail to list primes?
The proof shows some prime not on the original list divides $N$ — it does not produce that prime constructively in a useful sense. Starting with $\{2\}$ gives $N = 3$, prime — add $3$. Now $\{2, 3\}$ gives $N = 7$, prime — add $7$. $\{2, 3, 7\}$ gives $N = 43$ — add it. But $\{2, 3, 7, 43\}$ gives $N = 1807 = 13 \cdot 139$, so the procedure jumps to $13$ and skips $5, 11$ entirely. The argument proves infinitude, not enumeration.