## Catching primes

Submitted by plusadmin on June 1, 2008Prime numbers play a hugely important role as the fundamental building blocks of our number system — and they remain at the centre of some of the biggest mysteries of mathematics. Prime numbers are those whole numbers that can only be divided by themselves and the number 1. For example, 7 is a prime, but 6 is not, because 6 = 2 × 3. Non-primes are known as *composite numbers*

What makes primes the fundamental building blocks of our number system is the fact that *every* whole number can be written as a product of prime numbers. For example, the number 60 can be written as 60 = 2 × 2 × 3 × 5. What's more, there's only one way of doing this. *Any* expression for 60 as a product of primes involves precisely the same primes, but possibly arranged in a
different order.

Because of their important role in number theory, mathematicians make sustained efforts to discover the properties of the sequence of primes as a whole, and to identify further primes. We have known for over 2000 years that there are infinitely many primes, but there is no single formula which produces all prime numbers. However, there are procedures that systematically generate a list of all
the primes up to a given size. Here, we'll look at a method that does this *visually*, so that the sequence of primes unfolds before our eyes.

The method is called the *visual sieve* because it sieves out the composite numbers, leaving the primes behind. It was devised by Yuri Matiyasevich and Boris Stechkin, mathematicians working within the Steklov Mathematical Institute of the Russian Academy of Sciences. At the
heart of the method lies this diagram:

Figure 1: The visual sieve.

If you look closely, you might be able to see how this diagram relates to the primes. You might also notice that the diagram actually looks rather like a sieve — a nice convergence between the mathematical language and the object it describes! For now, though, we'll construct this diagram step by step. We'll discover how, as we follow the steps, the sequence of primes emerges.

### Making a sieve

We begin with a basic background diagram. We draw and -axes and mark the positive -axis with and the -axis with . These axes are shown below.

Figure 2: The axes.

On these axes we plot the curve . To clarify, at every point on this curve, we have . For example, two points lying on the curve are and . This type of curve is known as a *parabola*.

Figure 3: The parabola.

*upper*half of the parabola. We form the second set of points by marking the point for every whole number greater than or equal to , and labelling it with . These points all lie on the

*lower*half of the parabola.

Figure 4: Marking points.

The visual sieve diagram at the beginning contains a great many straight lines. We're now going to add these straight lines to our basic diagram in groups. We'll add each line by joining a pair of points marked on the parabola - always joining a point on the upper half with one on the lower half. We'll start by joining the points and , as shown below.

Figure 5: The first line.

We then join the pairs and ; and and . We continue, joining to every point we've marked on the lower half of the parabola. The result is shown below.

Figure 6: The first group of lines.

Next we do all this the other way up, joining to every point marked on the upper half of the parabola. We've now drawn in the two first groups of lines, and together they're shown below.

Figure 7: The first two groups of lines.

We now repeat this process, taking each of the points marked on the upper section, i.e. , , , and so on, and each point marked on the lower section, as our starting points. We've now completed the diagram, and the whole thing is pictured again below.

Figure 8: The complete visual sieve.

Let's pause for a moment to consider what we've actually done here. For each pair of whole numbers and , greater than or equal to , we've joined the points and . Let's give the line we've drawn a name - say . Now we're able to single out any line we like for our attention; for example, on the diagram below the line is marked in red.

Figure 9: The line L(3,4) marked in red.

### What's happening?

Let's now look at what the visual sieve is telling us. For the moment we'll focus our attention on the -axis. As we run our eye along it, from left to right, we'll pass over the markings for all the positive whole numbers. We can see that some of these whole number points are *crossed out* by a line (or several lines) passing through them - while others are not. At this point we might well wonder whether there's any significance in this. Well, it turns out that all the *composite* numbers are crossed out by lines, while all the *prime* numbers are not! The sequence of primes simply emerges before our eyes as we build up the diagram.

### Why does it work?

So why are the composites crossed out while the primes aren't? It's all because of one fundamental fact about the lines we've drawn on our diagram. Before we explore this fact let's recall our way of describing the lines we added. If and are any two whole numbers greater than or equal to , then is the line joining the points and . Now, instead of thinking about which points on the -axis are crossed out, and which aren't, we can turn the question around, and ask which point is crossed out by each line . It turns out that the line actually crosses out the point ! For example, the line joining and crosses out the number . This fact explains everything: any composite number can be factorised into , where each of and is at least . There may be more than one way of doing this, but we just need to choose one. Of course, the numbers and in this factorisation depend completely on the number we started with. If we then turn to the line , we know that it crosses out the number . But this is equal to itself, so we know that is crossed out! On the other hand, what happens to a prime number ? Well, we know that there's no way of factorising into with *both* and at least . So that means that there's no line which crosses out .

Very different things will happen depending upon whether and are equal or unequal. Let's look first at what happens if they're equal. The line now looks as shown in the diagram below. The scales and labels have been omitted so that we are representing *any* rather than a specific one.

Figure 10: The line *L(i,i)*.

We see that is a vertical line, and that any point lying on it has the same -coordinate, (or , since that's the same). So the point where meets the -axis also has -coordinate . But this is equal to , because and are equal. This is the result we expected, and that's dealt with what happens if is equal to .

From now on we can work on the assumption that the whole numbers and are not equal. We can draw the line , and note some important features. The figure below shows the situation when is greater than ; we will concentrate on this, because the situation when is less than is very similar.

Figure 11: The line *L(i,j)*.

Here we mark the two points and , and the point where the line meets the -axis, which we'll call . We want to find the -coordinate of this point , so let's give it the name . The next thing we'll do is to form two triangles using the points we've marked.

Figure 12: Forming two triangles.

The first triangle has corners at (this is the point on the upper half of the parabola) (the point directly below on the x-axis) and . One of its sides is a segment of the line , and it has a right angle at . The second triangle has corners at , (the point on the lower half of the parabola) and , (the point directly below ). Again, a segment of the line forms one of its sides, and the angle opposite that side is a right angle. We can now mark on the diagram the lengths of some of the sides of these triangles. The first triangle has vertical side of length and horizontal side of length . The second has vertical side of length and horizontal side of length .

Figure 13: Side lengths.

*similar*: one is a scaled-up version of the other. Another way of saying this is that the ratios between corresponding pairs of sides of the two triangles are the same. This translates into symbols as

### About the author

Abi grew up in the north of England, and moved south to study maths at Imperial College, London, and Queen Mary, University of London. She now teaches maths at the Open University and is working on a research project on on-line tutorials. Abi's main mathematical interest is group theory.