## Factors and Multiples

By now you should be comfortable with basic integer arithmetic and addition, subtraction and multiplication. Division is slightly different, because you can’t always divide any integer by any other. For example 17 divided by 3 is not a whole number – it is somewhere in between 5 and 6. You either have to give a remainder (2), or express the answer as a decimal number (5.66).

If you can divide a number **A** by a number **B**, without remainder, we say that **B** is a **factor** (or **divisor**) of **A**, and that **A** is a **multiple** of **B**. We often write **B**|**A**, where the vertical bar simply means *“divides”*.

For example, **7** × 3 = **21**, so **7** is a **21**, **21** is a **7**, and **7**|**21**.

In this short game you have to determine which numbers are factors or multiples, as fast as possible. Click the

### Factors and Multiples Quiz

In the next step we will learn various techniques to easily check if a number is divisible by another.

## Divisibility Rules

### Divisibility by 2 and 5

Every number is divisible by 1. To determine if a number is divisible by 2, we simply have to check if it’s even: any number that ends in 0, 2, 4, 6, or 8 is divisible by 2.

To see if a number is divisibility by 5 we similarly just have to check that its last digit is 0 or 5:

The reason why these rules for 2 and 5 are so simple has to do with our number system. The base of our number system is 10, which means that every digit in a number is worth 10 times as much as the next one to the right. If we take the number 6382 as an example,

6 | 3 | 8 | 2 |

=6000 | =300 | =80 | =2 |

Now we can separate the last digit of a number from all its other digits:

abcd | = | abc × 10 | + | d |

6382 | = | 638 × 10 | + | 2 |

Both 2 and 5 are factors of 10, so they will **abc × 10**, no matter what the values of **a**, **b** and **c** are. Therefore we only have to check the last digit: if **d** is divisible by 2 then **d** is divisible by 5 then the whole number is divisible by 5.

### Divisibility by 4 and 8

Unfortunately 4 doesn’t divide 10, so we can‘t just look at the last number – but 4 *does* divide 100, so we just have to slightly modify our rule from above. Now we write **ab****cd** = **ab × 100** + **cd**. We know that 4 will always divide **ab × 100**, so we have to look at the last

For example, **24** is divisible by 4 so **2735****24** **18** is not divisible by 4 so **1947****18**

The divisibility rules for 8 get even more difficult, because 100 is not divisible by 8. Instead we have to go up to

For example, **120** is divisible by 8 so **271****120** is also divisible by 8.

The easiest is the divisibility rule for 10: we just need to check if the

Practice exercises coming soon …

### Divisibility by 3, 6and 9

The divisibility rule for 3 is rather more difficult. 3 doesn’t divide 10, and it also doesn’t divide 100, or 1000, or any larger power of 10. Simply looking at the last few digits of a number isn’t going to work.

Instead we need to use the **digit sum** of a number, which is simply the sum of all its individual digits. For example, the digit sum of

Here we’ve highlighted all numbers which are multiples of three. You can see that their digit sums are always

So to determine if any number is divisible by 3, you just have to calculate its digit sum, and check if the result is also divisible by 3.

Next, let’s look at multiples of 9:

It seems that all the numbers divisible by 9 have a digit sum which is

Of course, these curious patterns for numbers divisible by 3 and 9 must have some reason – and like before it has to do with our base 10 numbers system. As we saw, writing the number **6****3****8****4** really means

**6 × 1000** + **3 × 100** + **8 × 10** + **4**.

We can split up each of these products into two parts:

**6 × 999 + 6** + **3 × 99 + 3** + **8 × 9 + 8** + **4**.

Of course, **9**, **99**, **999**, and so on are always divisible by 3 (or by 9). All that remains is to check that what’s left over is also divisible by 3 (or 9):

**6** + **3** + **8** + **4**

This just happens to be the digit sum! So if the

We’ve still skipped number 6 – but we’ve already done all the hard work. Remember that 6 = 2 × 3.

To check if a number is divisible by 6 we just have to check that it is divisible by 2 *any* number that is the product of two others. More on that later…

Unfortunately there is no simple divisibility rule for 7. However we now know the rules for all other numbers from 1 to 10, so let’s try a more advanced version of the divisibility game!

Practice exercises coming soon …

## Finding Factors

In many cases, it is not enough to find if a number is divisible by another – we need a list of *all* its divisors. For example, the divisors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60.

But we don’t want to have to try 60 different numbers and check which one is a divisor. Instead we can use a simple technique, which relies on the fact that divisors always appear in pairs.

In the case of 60 we have 60 = 1 × 60 = 2 × 30 = 3 × 20 = 4 × 15 = 5 × 12 = 6 × 10. Or, in a different notation,

60 | 1, | 2, | 3, | 4, | 5, | 6, | 10, | 12, | 15, | 20, | 30, | 60 |

To find all divisors of a number we simply start at both ends of this list, until we meet in the middle.

42 | 1, | 2, | 3, | 6, | 7, | 14, | 21, | 42 |

The only special case with this method is for square number: in that case, you will meet at just a single number in the middle, like 64 = 8 × 8.

## Prime Numbers

When calculating these divisor pairs, it can happen that a number doesn’t have any divisors except for the first pair. One example is 13 – its only divisors are 1 and 13 itself. These special numbers are called **Prime numbers**. They can’t be broken up into products of smaller numbers, which, in a way, makes them the “atoms of numbers”.

Note that 1 itself is *not* a prime number, so the first few prime numbers are 2, 3, 5, 7, 11, 13, …

Any number which is not prime can be written as the product of prime numbers: we simply keep dividing it into more parts until all factors are prime. For example,

84 | ||||||||

2 | × | 42 | ||||||

2 | × | 21 | ||||||

3 | × | 7 | ||||||

84 | = | 2 | × | 2 | × | 3 | × | 7 |

Now 2, 3 and 7 are prime numbers and can’t be divided further. The product 2 × 2 × 3 × 7 is called the **prime factorisation** of 84, and 2, 3 and 7 are its **prime factors**. Note that some primes, like 2 in this case, can appear multiple times in a prime factorisation.

Every integer has a prime factorisation and no two integers have the same prime factorisation. Furthermore, there is only a single way to write any number as a product of primes – unless we count different orderings of the primes. This is called the **Fundamental Theorem of Arithmetic** (FTA).

Using the FTA can make many problems in mathematics much easier: we divide numbers into their prime factors, we solve the problem for the individual primes, which can often be much easier, and then we combine these results to solve the initial problem.

## The Sieve of Eratosthenes

It turned out to be quite difficult to determine if a number is prime: you always had to find *all* its prime factors, which gets more and more challenging as the numbers get bigger. Instead, the Greek mathematician **Sieve of Eratosthenes**.

**2**. Any multiple of 2 can’t be prime, since it has 2 as a factor. Therefore we can cross out all multiples of 2.

**3**– again a prime number. All multiples of 3 can’t be prime, since they have 3 as a factor. Therefore we can cross these out as well.

**5**: it is a prime number and again we cross out all multiples of 5.

Now we can count that, in total, there are

## How many Prime Numbers are there?

Of course we can also use the Sieve of Eratosthenes to find larger prime numbers. There are 21 primes between 100 and 200, 16 primes between 200 and 300, 17 primes between 400 and 500 and only 11 between 10,000 and 10,100.

The primes seem to keep getting more and more spread out, but do they ever stop? Is there a *biggest* or a *last* prime number?

The ancient Greek mathematician

- Suppose there were only finitely many prime numbers.
*P*,*P*,*P*,*P*,*P* - Let us multiply all of them together, to get a very large number which we call
*N*.*N*=*P*×*P*×*P*×*P*×*P* - Now let’s think about
*N*+ 1. Any prime number that divides*N*can’t also divide*N*+ 1. And since all prime numbers we have found so far divide*N*, none of these can also divide*N*+ 1.*P*,*P*,*P*,*P*,P*N**P*,*P*,*P*,*P*,P*N*+ 1 - We know from the
Fundamental Theorem of Arithmetic that*N*+ 1, must have a prime factor. Either*N*+ 1 is itself prime, or there is some other new prime*P’*that divides*N*+ 1.*P’**N*+ 1 - In both cases we’ve found a new prime not in our original list – but we assumed that
*all*primes were in this list. - Clearly something went wrong! But since steps 2–4 were definitely valid, the only possibility is that our initial assumption in 1 was wrong. This means there must actually be infinitely many primes.

Euclid’s explanation is one of the first examples in history of a formal mathematical **proof** – a logical argument that shows a statement must definitely be true. This example is often called **proof by contradiction**: we start with an assumption, deduce something impossible, and thus know that our assumption must be incorrect.

## Large Primes

It is quite easy for a computer to check if a number is prime – simply by trying to divide it by all smaller numbers. But of course there are much cleverer and faster algorithms. Here you can try it yourself:

### Prime Checker

${result}

Throughout history, people have tried to calculate larger and larger primes. In 1460, the largest known prime number was 131,071. In 1772,

With the arrival of computers in the 20th century, calculating large primes became much faster and easier. Currently, the largest known prime number has 22,338,618 digits – you would need 5000 sheets of paper to print it out! It was discovered in September 2015 using a network of many thousands of computers around the world, run by volunteers, students and universities.

You might think that calculating these primes is just a waste of time – but, as we will see below, it turns out to be incredibly useful for computers to be able to quickly find large prime numbers.

Rather than checking if a large number is definitely prime, there are also much faster algorithms that tell you that a number is *almost certainly* prime. Here you can generate your own, large prime numbers:

### Prime Generator

Number of digits:

${result}

The Polish mathematician *“long and very boring”* meeting in 1963.

We write down all integers in a rectangular grid, starting with 1 in the middle and then spiralling outwards. Then we highlight all numbers which are prime.

So far, the Ulam spiral doesn’t look particularly exciting. But if we zoom out, interesting patterns emerge. Here are the primes up to 160,000:

Rather than appearing randomly, as one might expect, it seems that certain diagonals are much more popular with primes than others. This creates a curious “plaid” pattern.

*It turns out that these diagonals all correspond to certain quadratic equations which seem to generate prime numbers more often than average. However it is unknown why that would be the case…*

## The Least Common Multiple

Two runners are training on a circular racing track. The **first runner** takes **60** seconds for one lap. The **second runner** only takes **40** seconds for one lap. If both leave at the same time from the start line, when will they meet again at the start?

This question really isn’t about the geometry of the race track, or about velocity and speed – it is about multiples and divisibility.

The first runner crosses the start line after 60s, 120s, 180s, 240s, and so on. These are simply the **60**. The second runner crosses the start line after 40s, 80s, 120s, 160s, and so on. The first time both runners are back at the start line is after

What we’ve just found is the smallest number which is both a multiple of **40** and a multiple of **60**. This is called the **least common multiple** or **lcm**.

To find the lcm of any two numbers, it is important to realise that if **a** divides **b**, then **b** needs to have all the prime factors of **a** (plus some more):

12 | 60 | |

2 × 2 × 3 | 2 × 2 × 3 × 5 |

This is easy to verify: if a prime factor divides **a**, and **a** divides **b**, then that prime factor must *also* divide **b**.

To find the lcm of **40** and **60**, we first need to find the

40 | = | 2 | × | 2 | × | 2 | × | 5 | ||

60 | = | 2 | × | 2 | × | 3 | × | 5 |

Suppose that **X** is the lcm of **40** and **60**. Then **40** divides **X**, so 2, 2, 2 and 5 must be prime factors of **X**. Also, **60** divides **X**, so 2, 2, 3 and 5 must be prime factors of **X**.

To find **X**, we simply combine all the prime factors of **40_ and **{.m-blue}60__, but any duplicates we only need once:

**X** = 2 × 2 × 2 × 3 × 5

This gives us that **X** = 120, just like we saw above. Notice that if the same prime factor appears multiple times, like 2 above, we need to keep the maximum occurrences in one of the two numbers (3 times in **40** is more than 2 times in **60**).

Now we have a simple method for finding the lcm of two numbers:

ol.proof li Find the prime factorisation of each number. li Combine all prime factors, but only count duplicates once.

We can use the same method to find the lcm of three or more numbers at once, like **12**, **30** and **45**:

12 | = | 2 | × | 2 | × | 3 | ||||

30 | = | 2 | × | 3 | × | 5 | ||||

45 | = | 3 | × | 3 | × | 5 |

Therefore the lcm of **12**, **30** and **45** is 2 ×

A special case are prime numbers: the lcm of two different primes is simply heir

## The Greatest Common Factor

An architect is planning the floor for a large courtyard that measures 18m by 30m. She wants it to be covered in quadratic tiles, without any gaps or overlaps along the sides. What is the largest size of squares she can use?

Just like before, this question is not about geometry - it is about divisibility. The length of the sides of the tiles has to divide both 18 and 30, and the largest possible number with that property is **Greatest Common Divisor** or **gcd** of 18 and 30.

Once again, we can use the

18 | = | 2 | × | 3 | × | 3 | ||

30 | = | 2 | × | 3 | × | 5 |

Suppose that **X** is the gcd of **18** and **30**. Then **X** divides **18** so the prime factors of **X** must be among 2, 2 and 3. Also, **X** divides **30** so the prime factors of **X** must be among 2, 3 and 5.

To find **X**, we simply need to multiply all numbers which are prime factors of **18** and **30**:

**X** = 2 × 3 = 6.

Now we have a simple method for finding the gcd of two numbers:

ol.proof li Find the prime factorisation of each number. li Multiple the prime factors which are in both numbers.

Once again prime numbers are special: the gcd of two different primes is always

## LCM and GCD Applications

North America is home to various broods of cicadas. These have the curious property that they only emerge every few years during the summer to breed – the remaining time they spend underground.

For example, the cicadas in Florida and Mississippi appear every 13 years. The cicadas in Illinois and Iowa only appear every 17 years. But there are no cicadas with 12, 14, 15 or 16 year cycles.

Both 13 and 17 are prime numbers – and that has a very good reason. Imagine that there are predators in the forest which kill cicadas. These predators also appear in regular intervals, say every 6 years.

Now imagine that a brood of cicadas appears every

This number seems to be much larger if the cicada cycle is a prime number like 13 and 17. That‘s is because prime numbers don‘t share any factors with 6, so when calculating the lcm we don‘t cancel any duplicate factors.

Of course, cicadas have no idea what prime numbers are – but over millions of years, evolution has worked out that prime cycles are the safest. The predator animal seems to have gone extinct over time, but the prime number cycles remain.

## Primes in Cryptography

One of the most important modern applications of prime numbers is in a field of mathematics called **Cryptography**. For thousands of years, people have tried to conceal messages so that only the intended recipient could read them – this is called encryption. It is used by everyone from generals exchanging secret orders during wars to personal emails or online banking details.

People always tried to come up with better, more secure encryption methods, but after some time, they were all broken using yet more advanced algorithms. In the Second World War, the German army used the Enigma: a complex machine consisting of a keyboard, rotating wheels and plugs. It encrypted messages using one of 158 million million million possibilities (that’s a 158 followed by 18 zeros!). The code was widely belied to be unbreakable, but the British Secret Service, led by mathematician Alan Turing, built some of the first computers that managed to decode it.

Today’s computers are much more advanced, capable of trying millions of possibilities every second. To develop better encryption algorithms you have to find a mathematical operations that is difficult for a powerful computers. Computers are incredibly fast at addition, subtraction, multiplication and division. However, as it turns out, computers are very slow at factorising large integers into primes…

COMING SOON – RSA example with Alice and Bob

This encryption algorithm is called **RSA Cryptography**, after its three inventors, Ron Rivest, Adi Shamir and Leonard Adleman who published it in 1977. It turns out that a very similar method was known to the British Secret Service since 1973, but remained classified until much later.

Today, prime numbers are used by computers all over the world to exchange data. Whenever you send an email or visit a secure website, your phone or laptop quietly generates large prime numbers and exchanges public keys with other computers.

## Mysteries and Unsolved Problems

### The Goldbach Conjecture

In 1742, the German mathematician

### Goldbach Calculator

Pick any even number, to calculate how it

can be written as the sum of two primes.

${result}

Goldbach wrote about his observation in a letter to the famous mathematician **Goldbach Conjecture**.

Computers have checked that the Goldbach Conjecture works for every even number up to 4 × 10^{18} (that’s a 4 with 18 zeros), but mathematicians have still not found a proof that it works for *all* even integers. And that is a big difference, because there are infinitely many integers, so we couldn’t possibly check all of them.

Its apparent simplicity made the Goldbach conjecture one of the most famous unsolved problems in mathematics.

### Twin Primes

We have already seen that prime numbers get more spread out as they get bigger. But they always seem to appear completely random, and occasionally we find two primes right next to each other, just one number apart: these are called **Twin Primes**.

35,1113,4143,101103,20272029,108,377108,379,1,523,6511,523,653

The largest known pair of twin primes has an incredible 58,711 digits! But are there infinitely many twin primes, just like there are infinitely many primes? Nobody knows – the *Twin Prime conjecture* is another one of the many unsolved problems surrounding the primes.

### The Riemann Hypothesis

Mathematicians have spent many centuries exploring the pattern and distribution of prime numbers. They seem to appear completely randomly – sometimes there are huge gaps in between consecutive primes, and sometimes we find

When only 15 years old, the German mathematician

Along the x-axis you can see all integers. Whenever there is a prime, the *Prime Counting Function* increases by one. As we

Gauss noticed that the shape of this function looks very similar to the function

However, as you can see above, there is still a significant error between the actual number of primes, and Gauss’s approximation. In 1859, the mathematician *always* work. His idea became known as the **Riemann Hypothesis**.

Hundreds of mathematicians have tried to prove Riemann’s hypothesis, but all without success. It is often considered one of the most difficult and most important unsolved problems in mathematics. In 2000, the Clay Mathematics Institute named it one of six **Millennium Prize Problems** and promised $1,000,000 to any mathematician who solves it.