What’s So Cool About…
Primes
The ancient landscape of Greece
Primes were first investigated by the ancient Greeks. They were among the first people to realize that numbers can have an internal structure of factors. For example, 6 has the internal structure 2 × 3. Primes
appealed to the Greeks because their lack of such structure made them uniquely ‘simple’ and thus nearer to perfection.
prime: a number that has no factors except 1
and itself;
the first few primes are 2, 3, 5, 7, 11, 13, …
composite: any number greater than 1 which is not prime
The infinitude of primes
How many prime numbers are there? Powerful computers are discovering very large new primes, millions of digits long. Will the search ever be complete? This question was actually answered over 2000 years ago, by Euclid. Here’s an answer similar to Euclid’s:
Suppose that you know all the primes up to 269. Multiply them together and add one. If this new number is itself prime, it is obviously larger than 269 – so it must be a “new” prime. If the number is composite, it must have factors between 1 and itself, and some of these factors will be prime. What then?
Suppose, for example, that the prime 101 divides into your number. Is that correct? Let’s try it:
A quick prime test: Take the square root of a number, for example √269 ≈ 16.02.
Try all the prime numbers less than 16 as factors of 269. If none of them work, 269 is prime!
101 into 2 × 3 × 5 × …× 97 × 101 × 103 × … × 269 + 1
goes 2 × 3 × 5 × …× 97 × 101 × 103 × … × 269 remainder 1
101 doesn’t divide evenly into your number, and similarly neither do any of the other primes in your list.
So any prime factor of your number must come after your known list, and is therefore larger than 269.
In other words, however many primes you know, there are always more just around the corner. In fact, infinitely more!
Cryptic calculations
Primes play an important role in electronic security, basically because you can use them to encode messages. Here’s the trick:
1) pick two prime numbers, for example
3 and 11
2) calculate the numbers n = 3 × 11 = 33 and
m = (3 − 1) × (11 − 1) = 20
3) choose two numbers whose product, divided by m = 20,
has remainder 1; for example, choose d = 3 and e = 7,
since d × e = 21 = 20 + 1
4) number all the letter of your message, for example
“hi there” = 8-9-27-20-8-5-18-5
5) to encode: multiply each letter-number by itself d = 3 times,
and take the remainder after dividing by n; for example,
8 × 8 × 8 = 83 = 512
512 ÷ 33 = 15 remainder 17
So “hi there” becomes 17-3-20-14-17-26-24-26
6) to decode: multiply each code-number by itself e = 7 times;
for example,
17 × 17 … × 17 = 17⁷ = 410 338 673
410 338 673 ÷ 33 = 12 434 505 remainder 8
So 8 ® encoding ® 17
® decoding ® 8
The clever thing about this sort of encryption is that part of the “key” is public. If you publish just the numbers d = 3 and n = 33, anyone can encode a message. But only if you know the secret part, e = 7 and m = 20, can you decode messages. Now with small primes like these, it’s easy to see that 33 = 3 × 11, deduce that m = 20, and calculate that e must be 7. But if the two prime numbers you use are much bigger, factorising n to discover the primes becomes very difficult. For example, can you factorise 6 029 507, even using a calculator? And the numbers used in real-world applications of this cryptographic method are much, much larger still.
Explore Ř Try creating and using your own code. Experiment with the size of your two prime numbers. Use a calculator or spreadsheet software to help with the calculations.
Prime pairs and sequences
| 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
| |
Sometimes, primes appear in pairs that are just two apart, such as 11 and 13 or 41 and 43. A famous but unproven idea, the “prime pairs” conjecture, is that there are infinitely many prime pairs like this. A larger prime pair is 70 000 451 and 70 000 453. Websites about prime numbers feature prime pairs that are much larger still.
A similar idea, proven in 2003, is about longer sequences of primes that are separated by equal gaps, like this:
3, 5, 7 (sequence of 3, gap = 2)
11, 17, 23, 29 (sequence of 4, gap = 6)
17, 29, 41, 53 (sequence of 4, gap = 12)
In theory, this new idea says, however large a sequence length you choose, you can always find an evenly spaced sequence of primes at least that long. Proving this idea was very difficult; finding long sequences of evenly spaced primes in practice, though, is much harder still!
Messages in mathematese
Primes may be of great importance one day, if we ever receive radio messages from intelligent aliens. Obviously, their language, and perhaps even their visual sense, may be very different from our own. But mathematics is a form of universal truth, and since primes form just about the simplest sequence that could not possibly be natural, our radio telescopes might one day pick up a signal like this:
beep beep
beep beep beep
beep beep beep beep beep
beep beep beep beep beep beep beep
If we do, we will know for certain that the senders are intelligent.