Prime and composite numbers

If factors are the building blocks of a number, then primes are the atoms: numbers so basic that they cannot be broken any further. Every whole number is either a prime or a product of primes , there are no exceptions.

Concept

A prime number is a whole number greater than $1$ that has exactly two factors: $1$ and itself. The first few primes are:

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots$

A composite number is a whole number greater than $1$ that has more than two factors. The first few composites are:

$4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, \dots$

What about $1$? It has only one factor (itself), so it is neither prime nor composite. It is a special case.

A few quick facts:

• $2$ is the only even prime. Every other even number is divisible by $2$, so it has at least three factors ($1$, $2$, and itself).
• All primes after $2$ are odd, but not all odd numbers are prime (e.g. $9 = 3 \times 3$ is composite).
• There are infinitely many primes. This was proved by Euclid more than $2{,}000$ years ago , one of the most elegant proofs in mathematics.
• Primes thin out but never stop. There are $25$ primes below $100$, and only $4$ between $100$ and $113$.

The Sieve of Eratosthenes

How do we find all primes below, say, $100$? The Greek mathematician Eratosthenes invented a beautiful method called the sieve:

1. Write all numbers from $2$ to $100$.
2. Circle $2$. Cross out every other multiple of $2$ (i.e. $4, 6, 8, \dots, 100$).
3. The next un-crossed number is $3$. Circle it, cross out its multiples.
4. The next is $5$. Circle, cross out multiples.
5. Continue until you have processed every number up to $\sqrt{100} = 10$.
6. All remaining (circled) numbers are prime.

You only need to sieve with primes up to $\sqrt{n}$, because any composite $\leq n$ must have a prime factor $\leq \sqrt{n}$.

Why primes matter

Primes are the building blocks of all whole numbers. Just as every word is built from letters, every whole number greater than $1$ is built (uniquely) from primes. This is called the Fundamental Theorem of Arithmetic, and it is one of the cornerstones of mathematics.

Primes also have deep modern uses. The encryption that protects bank transactions and online passwords relies on the fact that multiplying two huge primes is easy, but reversing the process (finding the primes from the product) is, with current methods, almost impossibly slow.

Worked examples

Example 1. Is $51$ prime?

• Try divisors: $51 \div 3 = 17$. So $3$ is a factor.
• Factors of $51$: $1, 3, 17, 51$. More than two.
• $51$ is composite.

Example 2. Is $97$ prime?

• Check primes up to $\sqrt{97} \approx 9.8$: that means $2, 3, 5, 7$.
• $97$ is odd, not divisible by $3$ (digit sum $16$), does not end in $0$ or $5$, $97 \div 7 = 13.85\dots$ no.
• $97$ is prime.

Example 3. Find all primes between $20$ and $30$.

• Candidates: $21, 22, 23, 24, 25, 26, 27, 28, 29$.
• $21 = 3 \times 7$, composite. $22$ even, composite. $23$? Test $2, 3$: not divisible. $\sqrt{23} \approx 4.8$. Prime. $24$ even. $25 = 5^2$, composite. $26$ even. $27 = 3^3$, composite. $28$ even. $29$? Test up to $\sqrt{29} \approx 5.4$, so $2, 3, 5$: not divisible. Prime.
• Primes: $23, 29$.

Example 4. Twin primes are pairs of primes that differ by $2$, like $(3, 5)$, $(5, 7)$, $(11, 13)$. List twin primes below $50$.

• Below $50$: $(3, 5)$, $(5, 7)$, $(11, 13)$, $(17, 19)$, $(29, 31)$, $(41, 43)$.

Try it yourself

1. List all primes less than $50$.
2. Is $1$ prime? Why or why not?
3. Is $87$ prime? Show your working.
4. Find all composites between $30$ and $40$.
5. Is the sum of two odd primes always even? Why?
6. List the first $5$ primes greater than $50$.
7. Twin primes: find a pair between $50$ and $80$.
8. Tricky: are there three primes in a row (each differing by $2$) other than $3, 5, 7$? Argue why not.

Activity

Sieve $1$–$100$. On a sheet of paper, draw a $10 \times 10$ grid and write numbers $1$ to $100$ in it. Cross out $1$ (it is not prime). Circle $2$, cross out multiples of $2$. Then circle the next un-crossed ($3$) and cross out its multiples. Repeat with $5$, then $7$. Stop. Every uncrossed number is prime. Count them , you should find exactly $25$ primes below $100$.