Primes and Composites

Factors, the starting point

A quick reminder from the last lesson. A factor (or divisor) of a whole number $n$ is a whole number that divides $n$ leaving remainder $0$. To list the factors of $n$, you ask of each candidate “does it divide $n$ evenly?” The factors of $12$ are

because each of these divides $12$ with nothing left over, and no other whole number does. Two of those factors come free for every whole number greater than $1$. Every such number is always divisible by $1$ (one group containing everything) and by itself (one group the size of the whole number). So the real question, the one that sorts numbers into two camps, comes down to this. Does a number have only those two forced factors, or does it have more?

Defining prime and composite

This is the whole idea, stated carefully. We count only the distinct factors, and we work with whole numbers greater than $1$.

A whole number greater than $1$ is prime when it has exactly two distinct factors: $1$ and itself, and nothing in between. The number $7$ is prime because the only whole numbers that divide it are $1$ and $7$. Try anything else, say $2$, $3$, $4$, $5$, or $6$, and a remainder appears.

A whole number greater than $1$ is composite when it has more than two distinct factors. The number $12$ is composite because, beyond $1$ and $12$, the numbers $2, 3, 4,$ and $6$ also divide it. Having even one extra factor is enough to make a number composite.

Both of those claims are things you can check rather than take on trust. Below you choose how many dots there are and how many go in each row. When the rows come out even, the row width is a factor. When the last row is short, it is not, and the leftover dots are drawn hollow so you can count them.

Set the count to $12$ and walk the row width from $2$ up to $6$. Widths $2$, $3$, $4$ and $6$ all come out even, and only $5$ leaves anything over, so $12$ has factors to spare and is composite. Now set the count to $7$ and walk the same widths again. Every single one leaves a short row. Nothing between $1$ and $7$ divides it, which is exactly what makes $7$ prime, and you have now checked it rather than been told it.

Every whole number greater than $1$ falls into exactly one of these two groups, never both and never neither. Either its only factors are $1$ and itself (prime), or it has at least one more (composite). Here is the start of the list, sorted:

The word prime comes from the Latin for “first”, and the primes are first in the sense of being the simplest. They are the ones not built from smaller pieces. A composite number, as the name suggests, is “composed” of smaller factors.

Why 1 is neither prime nor composite

The number $1$ looks like it might be prime, since nothing divides it except $1$. But run it through the definition exactly. A prime needs two distinct factors. The number $1$ has only one factor, namely $1$ itself: the "$1$" and the “itself” are the same number, so they do not count twice.

The exclusion of $1$ is not a quirk of bookkeeping. Keeping $1$ out of the primes is what makes the primes behave as clean building blocks in the next lesson. If $1$ were prime, you could glue extra copies of it onto any factorization ($6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$) and never get a single, settled answer. Leaving $1$ aside keeps each number’s set of prime building blocks unique.

Why 2 is the only even prime

Look at the prime list again: $2, 3, 5, 7, 11, 13, \ldots$. After $2$, every entry is odd. That is no accident.

Try to find an even number past $2$ that survives the definition. Take $14$. Being even hands it $2$ as a factor for free, on top of the $1$ and the $14$ that every number is forced to have. Its factor list is $1, 2, 7, 14$, which is four factors, and a prime is allowed exactly two. That free gift of a $2$ arrives with every even number, which is what decides the general case.

This gives you a fast first filter. If a number bigger than $2$ ends in $0, 2, 4, 6,$ or $8$, you can declare it composite on sight, no division needed. The candidates for “prime” past $2$ are only the odd numbers, and even among those, plenty (like $9$, $15$, $21$) turn out to be composite.

Testing a number by trial division

To decide whether a number $n$ is prime, you hunt for a factor other than $1$ and $n$. Find even one and $n$ is composite; find none and $n$ is prime. The direct method is trial division: try the candidate divisors in turn and watch for a clean division. You do not need to test every number below $n$, and you do not need long division either. That is because the divisibility rules from the last lesson do most of the work.

Test the candidates in increasing order, $2, 3, 5, 7, \ldots$, and lean on the rules you already know:

• Try $2$: is the last digit even? If yes (and $n > 2$), then $n$ is composite.
• Try $3$: does the digit sum come out a multiple of $3$? If yes (and $n > 3$), then $n$ is composite.
• Try $5$: does it end in $0$ or $5$? If yes (and $n > 5$), then $n$ is composite.
• Try $7$, then the next candidates, dividing to check, until either a factor appears or you reach the stopping point in the next section.

You can skip every even candidate after $2$, since an even divisor would make $n$ even and you have already checked $2$. You can also skip multiples of $3$ after $3$, so in practice you test $2, 3, 5, 7, 11, 13, \ldots$, the primes themselves. A few small divisors are enough to settle even a fairly large number. The explanation is the stopping rule, which is the heart of the method.

The stopping rule: when can you quit?

Testing divisors one by one could go on a long time. The key shortcut is that you can stop early: once a candidate divisor $d$ grows large enough that $d \times d$ passes $n$, you are done. If nothing has divided $n$ by the time you reach that point, $n$ is prime. The reason is a fact about how factors come in pairs.

Watch the factors of $36$ do it. They arrive two at a time: $1$ with $36$, $2$ with $18$, $3$ with $12$, $4$ with $9$, and $6$ with $6$. Every one of those pairs has a partner of $6$ or less, and $6$ is the number whose square is $36$. So testing $2, 3, 4, 5, 6$ finds every pair there is. A divisor above $6$ could only be the larger partner of a pair you already caught by its smaller one.

In plain terms: keep testing divisors $d = 2, 3, 5, 7, \ldots$ only while $d \times d \le n$. As soon as $d \times d$ passes $n$, stop. For $n = 97$, you test $d = 2, 3, 5, 7$ (since $7 \times 7 = 49 \le 97$) and then consider $d = 11$, but $11 \times 11 = 121$, which is already past $97$, so $11$ is the signal to stop. None of $2, 3, 5, 7$ divided $97$, so $97$ is prime. You confirmed a prime by trying just four small divisors.

The pairing that $36$ showed you is the whole reason, and it holds for every number.

The Sieve of Eratosthenes

To find all the primes up to some limit at once, there is a method faster than testing each number on its own. That method has been known since antiquity as the Sieve of Eratosthenes (a way to find every prime below a limit by crossing out multiples). The idea is to start with every number and strain out the composites, leaving the primes behind. A sieve does the same, straining out what you do not want.

Write the whole numbers from $2$ up to your limit. Then repeat one move:

1. Circle the smallest number not yet crossed out. It is prime (nothing below it divided it, or it would already be crossed out).
2. Cross out every larger multiple of that number. They are all composite, since they have it as a factor.

The first prime is $2$, so circle it and cross out $4, 6, 8, 10, \ldots$. The next surviving number is $3$, so circle it and cross out $6, 9, 12, \ldots$. Then $5$, then $7$, and so on. By the stopping rule, once the circled prime times itself passes your limit, everything still standing is prime and you are finished.

Common mistakes