Divisibility and Primes

Prime numbers represent both the most basic properties and the most complex unsolved problems. Here you can learn about the building blocks of mathematics.

Remember to login to save your progress and get personalised content. This textbook works best on larger devices like tablets or laptops.

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).

0 1 2 3 4 5 6 7 8 9 10 11 12 3 3 12 3 3

12 is divisible by 3

0 1 2 3 4 5 6 7 8 9 10 11 12 4 4 4 10

10 is not divisible by 4

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 of 21, 21 is a of 7, and 7|21.

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

Factors and Multiples Quiz

${x}
is a
factor
multiple
neither
of
${y}

In the next section 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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,

6382
=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 is also divisible by 2. If 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 abcd = ab × 100 + cd. We know that 4 will always divide ab × 100, so we have to look at the last digits to check if a number if divisible by 4.

For example, 24 is divisible by 4 so 273524 divisible by 4, and 18 is not divisible by 4 so 194718 divisible by 4.

The divisibility rules for 8 get even more difficult, because 100 is not divisible by 8. Instead we have to go up to and look at the last digits of a number.

For example, 120 is divisible by 8 so 271120 is also divisible by 8.

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

Lets practice these divisibility rules for 2, 4, 5, 8 and 10 in this simple game:

Find the Divisor

Exercises under development…

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 ${13*n+123} is ${digitSumString(123 + 13*n)} = ${digitSum(123 + 13*n)} and the digit sum of 3524 is .

1
2
3
3
4
5
6
6
7
8
9
9
10
11
12
3
13
14
15
6
16
17
18
9
19
20
21
3
22
23
24
6
25
26
27
9
28
29
30
3
31
32
33
6
34
35
36
9
37
38
39
12
40

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:

9
9
18
9
27
9
36
9
45
9
54
9
63
9
72
9
81
9
90
9
99
18
108
9
117
9
126
9
135
9
144
9
153
9
162
9
171
9
180
9

It seems that all the numbers divisible by 9 have a digit sum which is divisible by 9.For example, the digit sum of 4752 is , so 4752 divisible by 9.

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 6384 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 digit sum is a multiple of 3, and we know that everything else is a multiple of 3, then the result must also be a multiple of 3.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

To check if a number is divisible by 6 we just have to check that it is divisible by 2 divisible by 3. Note that this happens to work for 6, but certainly not for 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!

Find the Divisor

Exercises under development…

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,

601,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.

421,2,3,6,7,14,21,42
For example, the first divisor pair of 42 is simply 1 and 42, and we write them down with much space in between.
After 1 at the beginning, we check if 2 divides 42. It does, and the corresponding pair is 42 ÷ 2 = 21.
Next, we check if 3 divides 42. It does, and the corresponding pair if 42 ÷ 3 = 14.
Now we check if 4 divides 42. It does not, however, so we move on.
5 also doesn’t divide 42 so we move on.
6 does divide 42 again. Its pair is 42 ÷ 6 = 7. Notice how we’ve met in the middle after only a few attempts, without having to test all numbers from 7 to 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.

Factorisation

Exercises under development…

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, …

Find the primes

Exercises under development…

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.

Find prime factorisations

Exercises under development…

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 Eratosthenes of Cyrene came up with a simple algorithm to find all prime numbers up to 100: the Sieve of Eratosthenes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
First we need to write down all numbers up to 100.
We know that 1 is not prime, so we delete it.
The smallest prime number is 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.
The next number in our list is 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.
The next number, 4, is already crossed out so we move on to 5: it is a prime number and again we cross out all multiples of 5.
The next prime number must be , since 6 is crossed out. Once more, we cross out all of its multiples.
The next prime number is . Notice, however, that all of its multiples are . The same is actually true for all other remaining numbers. Therefore all these remaining numbers must be prime.

Now we can count that, in total, there are prime numbers less than 100.

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 Euclid of Alexandria first proved that there are infinitely many prime numbers, using the following argument:

  1. Suppose there were only finitely many prime numbers.
    P, P, P, P, P
  2. Let us multiply all of them together, to get a very large number which we call N.
    N = P × P × P × P × P
  3. 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
  4. 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
  5. In both cases we’ve found a new prime not in our original list – but we assumed that all primes were in this list.
  6. Clearly something went wrong! But since steps 24 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, Leonard Euler showed that 2,147,483,647 is prime.

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.

The GIMPS Project (Great Internet Mersenne Prime Search) uses a network of computers around the world to find large prime numbers.

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: ${d}

${result}

The Polish mathematician Stanisław Ulam came up with a cool way to show the distribution of large prime numbers, while doodling during a "long and very boring" meeting in 1963.

37
36
35
34
33
32
31
38
17
16
15
14
13
30
39
18
5
4
3
12
29
40
19
6
1
2
11
28
41
20
7
8
9
10
27
42
21
22
23
24
25
26
43
44
45
46
47
48
49

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…

Cover of the March 1964 issue of Scientific American

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?

START 40 80 120 60 120

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 of 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 seconds.

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 prime factorisation of both:

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 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:

  1. Find the prime factorisation of each number.
  2. 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 × × 3 × 3 × = 180.

A special case are prime numbers: the lcm of two different primes is simply their , because they don’t have any common prime factors which would get “canceled”.

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?

The tiles have a size of ${x}m.
${result}

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 . This is called the Greatest Common Divisor or gcd of 18 and 30.

Once again, we can use the prime factorisation to calculate the gcd of any two numbers. Remember that any divisor of a number must have some of the prime factors of that number.

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:

  1. Find the prime factorisation of each number.
  2. Multiple the prime factors which are in both numbers.

Once again prime numbers are special: the gcd of two different primes is always , because they don’t share any prime factors.

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 ${n} years (${isPrime(n) ? 'prime' : 'not prime'}). The two animals would meet every ${lcm(n, 6)} years, which is the of 6 and ${n}.

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Time until cicadas and predators meet, for various different cicada cycle lengths.

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.

There are many other applications of lcm and gcd in nature, technology or everyday life…

LCM and GCD Word Problems

Exercises under development…

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.

German four-rotor Enigma machine

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…

RSA example with Alice and Bob coming soon…

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

In 1742, the German mathematician Christian Goldbach made a curious discovery: he noticed that all even integers (except 2) can be written as the sum of two prime numbers. For example, 8 = 5 + 3 and 24 = 13 + 11. This is quite surprising, because primes are defined using multiplication and factors – and shouldn’t have much to do with addition.

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 Leonhard Euler, but neither of them was able to prove it. It became known as the Goldbach Conjecture.

Computers have checked that the Goldbach Conjecture works for every even number up to 4 × 1018 (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 possible check all of them.

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

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.

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 twin primes right next to each other.

When only 15 years old, the German mathematician Carl Friedrich Gauss had a groundbreaking new idea: he counted the number of primes up to a certain point, and showed the results in a chart:

Along the x-axis you can see all integers. Whenever there is a prime, the Prime Counting Function increases by one. As we zoom out, the blue line becomes very smooth.

Gauss noticed that the shape of this function looks very similar to the function xlog(x). He predicted that the two functions are always “approximately similar”, and this was proven in 1896.

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 Bernhard Riemann discovered an approximation that looked much better, but he wasn’t able to prove that that would 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.

Next step
… or click the “Space” key to proceed!
Show all