# Divisibility and PrimesPrime Numbers

When calculating these factor pairs, it can happen that a number doesn’t have any factors except for the first pair. One example is 13 – its only factors 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.