Changer de langue

English中文DeutschRomânăTürkçe

Connectez-vous à Mathigon

ou

Nouveau compte     Réinitialiser le mot de passe     

Divisibility and Primes
Factors and Multiples
Divisibility Rules
Prime Numbers
The Distribution of Primes
Lowest Common Multiples
Greatest Common Factors

Partager

Réinitialiser la progression

Cela supprimera votre progression et vos données de discussion pour tous les chapitres de ce cours, et ne peut pas être annulé!

Glossaire

Sélectionnez l'un des mots clés à gauche…

Divisibility and PrimesPrime Numbers

Temps de lecture: ~20 min

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

Archie