Prime numbers are the building blocks of multiplication: every integer greater than 1 has a unique prime factorisation, apart from the order of the factors. For example, 360 = 2³ · 3² · 5. How can we recognise primes, and which patterns can we actually prove?
1. What is a prime number?
An integer greater than 1 is prime if it has exactly two positive divisors: 1 and itself. If it has other divisors, it is composite. The number 1 is neither prime nor composite. The number 2 is the only even prime: every other even integer greater than 2 is divisible by 2.
The primes up to 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
2. Why stop at the square root?
If n = a · b is composite, at least one factor is at most √n: if both were larger, their product would exceed n. We therefore only need to look for prime divisors not exceeding √n.
For 97, since 9 < √97 < 10, we test only 2, 3, 5 and 7. None divides 97, so it is prime. Equality matters: for 49 we must test 7 as well.
3. The sieve of Eratosthenes
To find every prime up to a limit N, we can process numbers together instead of checking each separately.
- Write the integers from 2 to N, initially all unmarked.
- Take the smallest unmarked number p: it is prime.
- Mark its multiples starting at p². Smaller multiples have already been removed by earlier primes.
- Move to the next unmarked number and continue while p² ≤ N.
- The numbers left unmarked are exactly the primes.
Up to 50, we only need to remove multiples of 2, 3, 5 and 7, starting at 4, 9, 25 and 49 respectively.
4. The 6k − 1 and 6k + 1 pattern
Every integer has remainder 0, 1, 2, 3, 4 or 5 when divided by 6. Remainders 0, 2 and 4 give even numbers; remainder 3 gives multiples of 3. A prime greater than 3 can therefore only have remainder 1 or 5.
p > 3 prime ⇒ p = 6k − 1 or p = 6k + 1This is necessary, not sufficient. The number 25 is 6 · 4 + 1, but composite; 35 is 6 · 6 − 1 and is also composite. The pattern filters candidates, but does not prove primality.
5. Gaps between primes
Consecutive prime gaps vary: from 2 to 3 the gap is 1, from 3 to 5 it is 2, from 7 to 11 it is 4, and from 23 to 29 it is 6. After 2 all these gaps are even, since we subtract two odd numbers.
There are runs of consecutive composite numbers of any desired length. For any integer m ≥ 2, consider:
(m + 1)! + 2, (m + 1)! + 3, …, (m + 1)! + (m + 1)These are m consecutive composite numbers: the term ending in +j is divisible by j, because the factorial is also divisible by j. Here q! = 1 · 2 · … · q. For m = 3 we get 26, 27 and 28.
6. Why primes never run out
Suppose we have listed all primes, from p₁ to pₖ, and construct M = p₁ · p₂ · … · pₖ + 1. Division by any prime in the list leaves remainder 1. Yet M, being greater than 1, has a prime divisor, which must lie outside the list. This is a contradiction!
M itself need not be prime. For example, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509. The proof guarantees a new prime divisor, not that every such product plus one is prime.
Put the patterns to the test
Is 221 prime?
Show the solution
No:
221 = 13 · 17. Since √221 lies between 14 and 15, testing primes up to 13 is enough to find a divisor.Can p, p + 2 and p + 4 all be prime?
Show the solution
Yes: 3, 5, 7. This is the only triple: one of the three numbers is divisible by 3, so it must equal 3 to be prime. Placing 3 second or third does not give three primes.
For which primes p is p² + 2 also prime?
Show the solution
Only p = 3, giving 11. Every prime other than 3 has remainder 1 or 2 modulo 3, so its square has remainder 1. Thus p² + 2 is divisible by 3 and greater than 3, hence composite.
Does n² + n + 41 always produce primes for nonnegative integers n?
Show the solution
No. Although early values look promising, n = 40 gives
1600 + 40 + 41 = 1681 = 41². Many successful examples cannot replace a proof.
Exploring a pattern means forming a conjecture, seeking counterexamples and identifying what constitutes a proof. A useful regularity is not always an exception-free rule.