Divisibility and Primes

Every whole number bigger than 1 is built out of primes the way every molecule is built out of atoms. Primes are the indivisible pieces — the numbers that cannot be broken down any further — and understanding them is the entry point to all of number theory. Before we can talk about primes, though, we need a precise language for what "divides" actually means. This page builds that language from the ground up: the divisibility rules that let you factor numbers in your head, the exact definition of a prime, Euclid's stunning 2,300-year-old proof that the primes never run out, and the Sieve of Eratosthenes, an algorithm so clean it is still used today.

Learning Objectives

• State precisely what it means for one integer to divide another.
• Apply and explain why the divisibility rules for 2, 3, 4, 5, 6, 8, 9, 10, and 11 work.
• Distinguish prime, composite, and the special cases 0 and 1.
• Reconstruct Euclid's proof that there are infinitely many primes.
• Use the Sieve of Eratosthenes to list every prime up to a given bound and know why you only sieve up to the square root.

Quick Answer

An integer $a$ divides an integer $b$ (written $a \mid b$) when $b = a \times k$ for some integer $k$ — that is, the division leaves no remainder. A prime is a whole number greater than 1 whose only positive divisors are 1 and itself; a composite has at least one other divisor. The number 1 is neither. Divisibility rules are shortcuts, grounded in place value, for testing divisibility without long division. Euclid proved around 300 BCE that primes are infinite: assuming a complete finite list leads to a contradiction. The Sieve of Eratosthenes lists all primes up to $n$ by repeatedly crossing out multiples, and you only need to sieve with primes up to $\sqrt{n}$.

Where It Came From

The study of divisibility is as old as counting itself, because the practical problem came first: how do you share things fairly? If 12 loaves must be split among some number of people with none left over, you need to know the divisors of 12. Egyptian and Babylonian scribes worked with these ideas for trade, taxation, and calendar-making thousands of years ago.

The Greeks turned this practical knowledge into a theory. Around 300 BCE, Euclid collected the mathematics of his era into the Elements, and Books VII–IX are devoted entirely to number theory. Euclid needed a rigorous foundation because the Greeks had discovered something disturbing: not all quantities are ratios of whole numbers (irrationality). This pushed them to be extremely careful about what whole numbers are and how they factor. Out of that care came the definition of a prime and Euclid's famous proof of their infinitude — one of the first proofs in history to establish that something goes on forever using pure logic rather than examples.

A generation or so later, Eratosthenes of Cyrene (c. 276–194 BCE), the polymath librarian at Alexandria who also measured the circumference of the Earth, gave a mechanical procedure for finding primes. His "sieve" answered the complementary question: Euclid told us primes never end, but how do we actually list the ones we have? The need was real — mathematicians wanted tables of primes, and hand-computing each one by trial division is exhausting. The sieve trades multiplication for simple counting, and it remains the fastest simple method for generating all small primes.

Divisibility: The Exact Definition

We say $a$ divides $b$, written $a \mid b$, if there is an integer $k$ such that $b = a \times k$. Equivalently, $b$ divided by $a$ leaves remainder 0. We call $a$ a divisor (or factor) of $b$, and $b$ a multiple of $a$.

A few consequences follow immediately:

• Every integer divides 0, because $0 = a \times 0$. But 0 divides only 0.
• 1 divides everything, since $b = 1 \times b$.
• If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$ and $a \mid (b - c)$. This "linearity" is the engine behind Euclid's algorithm and most divisibility proofs.

Worked example. Does $7 \mid 91$? We look for an integer $k$ with $91 = 7k$. Since $7 \times 13 = 91$, yes: $k = 13$, so $7 \mid 91$. Does $7 \mid 92$? Now $92 = 7 \times 13 + 1$, remainder 1, so no.

Divisibility Rules and Why They Work

The rules are not magic — they all come from place value. A number like $3\,472$ means $3\times1000 + 4\times100 + 7\times10 + 2$. Because $10, 100, 1000, \ldots$ have known remainders when divided by small numbers, we can test the whole number by testing its digits.

Divisor	Rule	Why
2	Last digit is even	10 is divisible by 2, so only the units digit matters
3	Digit sum divisible by 3	$10 \equiv 1$, so each power of 10 leaves remainder 1
4	Last two digits divisible by 4	100 is divisible by 4
5	Ends in 0 or 5	10 is divisible by 5
6	Divisible by 2 and 3	6 = 2 × 3 with 2, 3 coprime
8	Last three digits divisible by 8	1000 is divisible by 8
9	Digit sum divisible by 9	$10 \equiv 1 \pmod 9$ too
10	Ends in 0	10 divides 10
11	Alternating digit sum divisible by 11	$10 \equiv -1 \pmod{11}$

Why the rule for 3 (and 9) works. Since $10 = 9 + 1$, dividing any power of 10 by 3 or 9 leaves remainder 1. So $3\,472 = 3\times(999+1) + 4\times(99+1) + 7\times(9+1) + 2$. Every "9…9" part is divisible by 3, leaving exactly the digit sum $3+4+7+2 = 16$. Because 16 is not divisible by 3, neither is 3,472. (And $3\,471$, whose digits sum to 15, is divisible by 3.)

Worked example — the rule for 11. Test $90\,816$. Alternate signs from the right: $6 - 1 + 8 - 0 + 9 = 22$. Since $11 \mid 22$, we conclude $11 \mid 90\,816$. Check: $90\,816 \div 11 = 8\,256$ exactly. The rule works because $10 \equiv -1 \pmod{11}$, so consecutive place values alternate between $+1$ and $-1$.

Primes and Composites

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. A composite number is an integer greater than 1 that has at least one divisor other than 1 and itself. The first several primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.

Two edge cases trip everyone up:

• 1 is not prime. It has only one divisor (itself), not two. More importantly, if 1 were prime, factorizations would not be unique — you could write $6 = 2\times3 = 1\times2\times3 = 1\times1\times2\times3$. Excluding 1 keeps the Fundamental Theorem of Arithmetic clean: every integer above 1 factors into primes in exactly one way.
• 2 is the only even prime. Every other even number has 2 as a divisor, so it is composite.

Worked example — is 221 prime? We trial-divide by primes up to $\sqrt{221} \approx 14.9$: 2 (no, odd), 3 (digit sum 5, no), 5 (no), 7 ($221 = 7\times31 + 4$, no), 11 (alternating sum $1-2+2 = 1$, no), 13 ($13 \times 17 = 221$ — yes!). So $221 = 13 \times 17$ is composite. Notice we never had to test past 14: if $221$ had a factor larger than its square root, the paired factor would be smaller than the square root and we would have already found it.

Euclid's Proof That Primes Never End

Here is the argument that has amazed students for two millennia. Euclid shows that no finite list can contain all the primes.

Suppose, for contradiction, that there are only finitely many primes, and list them all: $p_1, p_2, p_3, \ldots, p_n.$

Now form the number $N = (p_1 \times p_2 \times p_3 \times \cdots \times p_n) + 1.$

$N$ is bigger than every prime on our list, so by assumption it must be composite, meaning some prime $p_i$ from the list divides it. But $p_i$ also divides the product $p_1 \times \cdots \times p_n$. If a prime divides both $N$ and the product, it must divide their difference — and that difference is exactly $N - (p_1\cdots p_n) = 1$. No prime divides 1. Contradiction.

Therefore our assumption was false: there are infinitely many primes.

Worked illustration. Suppose someone claimed the only primes were $2, 3, 5, 7, 11, 13$. Then $N = 2\times3\times5\times7\times11\times13 + 1 = 30\,031$. Is $N$ itself prime? Not necessarily — and that is a subtle point. Here $30\,031 = 59 \times 509$. Neither 59 nor 509 is on the list, so we have found new primes either way. The proof does not claim $N$ is prime; it claims $N$ forces the existence of a prime outside the list.

The Sieve of Eratosthenes

To list every prime up to $n$, Eratosthenes' method is beautifully mechanical:

1. Write the numbers $2, 3, 4, \ldots, n$.
2. Start with the first uncrossed number (2). It is prime. Cross out every multiple of it beyond itself.
3. Move to the next uncrossed number; it is the next prime. Cross out its multiples.
4. Repeat. You can stop once your current prime exceeds $\sqrt{n}$ — everything still uncrossed is prime.

Worked example — primes up to 30. $\sqrt{30} \approx 5.5$, so we only sieve with 2, 3, and 5.

• Cross multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
• Next uncrossed is 3. Cross 6, 9, 12, 15, 18, 21, 24, 27, 30 (some already gone).
• Next uncrossed is 5. Cross 10, 15, 20, 25, 30.
• Next uncrossed is 7, but $7 > 5.5$, so we stop.

Survivors: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — the ten primes below 30.

Why stop at $\sqrt{n}$? Any composite $m \le n$ has a prime factor no larger than $\sqrt{m} \le \sqrt{n}$ (its smallest prime factor). So every composite is crossed out by some prime up to $\sqrt{n}$; nothing composite can slip through. A small optimization: when sieving prime $p$, start crossing at $p^2$, since smaller multiples were already crossed by smaller primes.

Real-World Applications

• Cryptography. RSA encryption, which secures much of internet banking and messaging, relies on the fact that multiplying two large primes is easy but factoring the product back is astronomically hard. The whole system rests on the primes Euclid guaranteed exist.
• Hashing and data structures. Hash tables often use a prime number of buckets because primes spread keys evenly and reduce clustering from patterned inputs.
• Error-correcting codes and check digits. ISBNs and bank routing numbers use divisibility (the mod-11 and mod-10 rules) to catch typos automatically.
• Gears and cycles. Engineers choose gear-tooth counts that are coprime so that the same teeth do not repeatedly mesh, spreading wear evenly.

Common Mistakes

1. Thinking 1 is prime. Why wrong: a prime must have exactly two distinct positive divisors; 1 has only one. Correction: 1 is a unit — neither prime nor composite — and excluding it is what makes prime factorization unique.
2. Believing Euclid's $N$ is always prime. Why wrong: $2\times3\times5\times7\times11\times13 + 1 = 30\,031 = 59\times509$ is composite. Correction: the proof only guarantees a new prime exists (as a factor of $N$), not that $N$ itself is prime.
3. Sieving or trial-dividing all the way up to $n$. Why wrong: it wastes enormous effort. Correction: stop at $\sqrt{n}$ — a composite number always has a factor at or below its square root, so nothing is missed.

Comparison and Connections

Concept	Meaning	Key point
Factor / divisor	Divides evenly, remainder 0	Comes in pairs around $\sqrt{n}$
Multiple	Result of multiplying by an integer	The "reverse" of a factor
Prime	Exactly two divisors	Building blocks
Composite	More than two divisors	Products of primes
Coprime	Share no common factor but 1	GCD equals 1

Divisibility rules connect to modular arithmetic (each rule is a statement about remainders mod that divisor). Primes lead directly to the Fundamental Theorem of Arithmetic and to the greatest common divisor, computed by the Euclidean algorithm. The sieve is your first taste of an algorithm with a provable running time.

Practice Questions

Recall

List all primes between 40 and 60. Answer: 41, 43, 47, 53, 59.

Understanding

Explain in one sentence why the divisibility rule for 9 uses the digit sum. Guidance: Because $10 \equiv 1 \pmod 9$, every power of 10 leaves remainder 1, so a number and its digit sum have the same remainder mod 9.

Application

Use the rule for 11 to test whether 3,829,684 is divisible by 11. Answer: Alternating sum from the right: $4 - 8 + 6 - 9 + 2 - 8 + 3 = -10$. Not divisible by 11.

Analysis

A composite number $n$ is claimed to have no prime factor at or below $\sqrt{n}$. Show this is impossible. Guidance: Write $n = a \times b$ with $1 < a \le b$. If both exceeded $\sqrt{n}$ then $ab > n$, a contradiction, so the smaller factor $a \le \sqrt{n}$, and its prime divisor is smaller still.

FAQ

Is 2 really prime? It feels too small. Yes. It has exactly two divisors, 1 and 2, which is the definition. It is simply the unique even prime.

Why isn't 1 prime — who decided that? It is a definition chosen so that factorization into primes is unique. If 1 counted, you could pad any factorization with extra 1s.

Does Euclid's proof actually build the "next" prime? No. It proves a prime outside any finite list must exist, but the number $N$ it constructs is often composite; the new prime hides among $N$'s factors.

How far do I have to check to confirm a number is prime? Only up to its square root. If nothing at or below $\sqrt{n}$ divides it, $n$ is prime.

Is there a largest known prime? There are infinitely many primes, so there is no largest one at all. But the largest one humans have written down keeps growing — currently these are enormous Mersenne primes found by distributed computing.

Quick Revision

• $a \mid b$ means $b = a \times k$ for some integer $k$ (remainder 0).
• Prime: exactly two divisors. Composite: more than two. 1 is neither; 2 is the only even prime.
• Divisibility rules come from place value: 3 and 9 use digit sums; 11 uses the alternating sum.
• To test primality or sieve, only go up to $\sqrt{n}$.
• Euclid: assume finitely many primes, form $N = p_1\cdots p_n + 1$; a prime dividing $N$ can't be on the list — contradiction.
• Sieve of Eratosthenes: cross out multiples starting at $p^2$; survivors are prime.

Related Topics

Prerequisites

• Number Theory overview

Related Topics

• Modular arithmetic and remainders
• Greatest common divisor and the Euclidean algorithm

Next Topics

• The Fundamental Theorem of Arithmetic and prime factorization