Factors, primes and how to test them

In Discover you met factors, multiples, primes and composites through laddoos, tiles and a sieve. This layer makes those ideas precise and gives you reliable methods:

• how to find every factor of a number without missing any, and know when to stop;
• how to decide whether a large number like 221 or 437 is prime, with the least possible work;
• the divisibility rules for 2, 3, 4, 5, 6, 8, 9, 10 and 11;
• exactly what twin primes and co-prime numbers are, with their tricky cases;
• how to break any composite number into primes with a factor tree.

Along the way you will meet the mix-ups that catch most learners, so you can avoid them.

Mathematicians use several phrases for the same fact. If 3 × 5 = 15, then all of these are true:

• 3 is a factor of 15 (also: 3 is a divisor of 15).
• 15 is a multiple of 3.
• 15 is divisible by 3 (15 ÷ 3 = 5 with remainder 0).
• 3 divides 15. (Older books and later maths write this as 3 | 15, read "3 divides 15". The vertical bar is not a division sign.)

All four sentences are about whole numbers and exact division. We say 2 is not a factor of 15, even though 15 ÷ 2 = 7.5, because 7.5 is not a whole number: sharing 15 into 2 equal whole groups leaves 1 over.

The safest way to list all factors is the factor-pair method:

1. Write 1 and the number itself as the first pair.
2. Try 2, 3, 4, 5, … in order. Whenever one divides exactly, write it with its partner (the answer of the division).
3. Stop when the number you are trying is bigger than its partner would be, in other words, when the pairs meet in the middle.

The stopping rule is what makes this method fast. For 100 you only need to try up to 10, because 10 × 10 = 100. Any factor bigger than 10 must pair with a factor smaller than 10, and you have already found all of those.

When two numbers are in play, we often want what they share.

• A common factor of 12 and 18 divides both. Factors of 12: 1, 2, 3, 4, 6, 12. Factors of 18: 1, 2, 3, 6, 9, 18. Common factors: 1, 2, 3, 6. The largest, 6, is the highest common factor (HCF).
• A common multiple of 4 and 6 is in both times tables. Multiples of 4: 4, 8, 12, 16, 20, 24, … Multiples of 6: 6, 12, 18, 24, 30, … Common multiples: 12, 24, 36, … The smallest, 12, is the lowest common multiple (LCM).

Two numbers always have a finite list of common factors (1 is always on it) and an endless list of common multiples (their product is always on it). The HCF and LCM get their own topic; here they matter because they explain co-prime numbers, later in this layer.

Now the three definitions can be stated exactly, for every counting number n:

• n is prime if it has exactly two factors, 1 and n. That forces n to be bigger than 1.
• n is composite if it has more than two factors. Equivalently, n can be written as a × b where both a and b are whole numbers bigger than 1.
• n = 1 has exactly one factor and is neither.

A useful way to say the composite rule: a composite number has a factor that is neither 1 nor itself. Find one such factor and you have proved the number is composite. To prove a number is prime, you must show that no such factor exists, which is harder. The rest of this layer is about doing that efficiently.

To find every prime up to 100, write the numbers 1 to 100, cross out 1, then for each prime in turn cross out its multiples. The surprise is how early you can stop: after 7.

Here is why. Every composite number up to 100 is a × b with a ≤ b. If both a and b were bigger than 10, then a × b would be bigger than 10 × 10 = 100. So every composite up to 100 has a factor that is 10 or less, and therefore a prime factor of 10 or less: 2, 3, 5 or 7. The sieve with 2, 3, 5 and 7 catches all of them.

The same reasoning tells you where to start crossing out for each prime. For 7, start at 7 × 7 = 49: the smaller multiples 14, 21, 28, 35 and 42 have a smaller prime factor (2, 3 or 5) and are already crossed out.

What remains are the 25 primes up to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

To test a single number n for being prime, you do not need to sieve. Use trial division:

1. Divide n by the primes 2, 3, 5, 7, 11, 13, … in order.
2. If one of them divides exactly, n is composite. Stop.
3. Stop trying once the prime squared is bigger than n. If nothing has divided n by then, n is prime.

The stopping rule is the sieve's reason again. If n = a × b with a ≤ b, then a × a ≤ a × b = n, so the smaller factor a is at most √n (the square root of n, the number that multiplied by itself gives n). If no prime up to √n divides n, then n has no factor pair at all except 1 × n.

You never need to try composite numbers like 4, 6 or 9. If 9 divided n, then 3 would too, and you would already have found it.

Trial division is faster with divisibility rules: quick tests that tell you whether a small number divides a big one, often just by looking at its digits. In this layer you learn how to use them. The Deepen layer shows why each one works, using place value.

Twin primes are two primes whose difference is exactly 2. Up to 100 there are 8 pairs:

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73).

Some facts to be precise about:

• (2, 3) is not a twin pair: they differ by 1. It is the only pair of primes that are next-door neighbours.
• 5 belongs to two pairs, (3, 5) and (5, 7). That makes 3, 5, 7 the only set of three primes each 2 apart, called a prime triplet in this sense. The Investigate layer finds out why there can never be another one.
• The number between a twin pair (4, 6, 12, 18, 30, 42, 60, 72) is always a multiple of 6 after the first pair. Check it for yourself.
• Up to 1,000 there are 35 twin pairs. Nobody knows whether there are infinitely many: this is the twin prime conjecture, still unsolved.

Two numbers are co-prime (also called relatively prime) when their highest common factor is 1: they share no factor except 1.

Precise facts, each worth remembering:

• Co-prime is a property of a pair (or a set) of numbers, never of one number.
• The numbers need not be prime: 8 and 15 are co-prime, and so are 4 and 9, 14 and 25, 16 and 27.
• Two different primes are always co-prime, since each has only itself and 1 as factors.
• Consecutive numbers, like 20 and 21 or 99 and 100, are always co-prime. (A number that divided both would have to divide their difference, 1.)
• Two even numbers are never co-prime: they share the factor 2.
• 1 is co-prime to every number.
• A prime p and any number that is not a multiple of p are co-prime: 7 and 30 are, but 7 and 35 are not.

Every composite number can be split into smaller factors, and those can be split again, until only primes are left. Writing a number as a product of primes is called its prime factorisation.

A factor tree is a neat way to do it. Write the number at the top. Split it into any factor pair (not 1 × itself). Keep splitting every composite branch. Stop when every leaf at the bottom is a prime. Then multiply the leaves together.

You can also use repeated division: divide by the smallest prime that works, write down the result, and repeat until you reach 1. This is sometimes called the division ladder.

We use index form to write repeated primes neatly: 2 × 2 × 2 is written 2³ (read "2 cubed" or "2 to the power 3").