Home > Number theory > Dialogues

# Prime Problems

(Alex and Charlie are explaining prime numbers to their friend Simon.)

Alex: A prime number is one that is only divisible by itself and 1, for example 13.

Simon: Hmm... 13 is divisible by 1 and 13. What about 2? No, not 2. 3? Definitely not. 4? No, but I can’t stop now. 5?

Charlie: Apparently you can stop once you reach the square root of the number. The square root of 13 is between 3 and 4.

Simon: So I only need to check up to 3? .

Alex: Although it does get a lot harder as numbers get bigger and bigger. Try doing it for a 200-digit number. But some pretty big primes have been found. I can’t write them out directly but I can express them in terms of powers of 2. 2431126089-1 is quite a big prime. They’ve recently discovered an even bigger one. I think it was 257885161-1. But Euclid proved that there is no biggest prime number.

Charlie: How did he prove it?

Alex: Simple. If there is a biggest prime number, you can write down a list. Multiply all numbers in the list. The result is a number that is divisible by every prime number on the list. Now add 1. This new number does not divide any prime number on the list and is not on the list itself. Is it prime? If it is, then it is not on our list. If it is not, then it must be divisible by a prime number. But it is not divisible by any number on the list so the prime numbers it is divisible by are not on the list. Either way, you have prime numbers that are not on the list. Of course, this is too cumbersome to be practical, but it works in principle.

Simon: If I were you, I’d just add on the numbers that are not on the list, although I have no clue about how to obtain such a list.

Charlie: Then you could do the same to that list and so on. Your list will never be complete.

(Simon sits down and draws a spiral)

Charlie: Try drawing numbers on it.

Alex: Here's a challenge. Colour every prime number black.

Simon: Long black diagonal lines have appeared on the paper.

Alex: You’ve just rediscovered the Ulam spiral!

Simon: Who’s Ulam?

Alex: He was a Polish mathematician who lived from 1909 to 1984. He created the Monte Carlo method, which involves making random simulations to estimate probabilities. He also invented lucky numbers which are similar to prime numbers.

Charlie: What’s a lucky number?

Alex : Start with 1. It is a lucky number. The next number is 2. Remove every second number. The next number is 3. It is lucky. Remove every third number. The next number is 7. It is lucky. Remove every seventh number and so on. Lucky numbers are very similar to prime numbers.

Simon: But what about my spiral?

Alex: Ulam was doodling during the presentation of a “long and very boring paper” when he found this pattern, which seems to imply that certain quadratic equations had a large number of prime solutions. There are also clear diagonal gaps and horizontal and vertical gaps and lines too.

 A large Ulam spiral showing the tendency of primes to lie on diagonals.

Charlie: Remember when you told us about large prime numbers? Why are they all of the form 2p-1?

Alex: You mean Mersenne primes?

Simon: What are Mersenne primes?

Alex: Those are just prime numbers of that form. If you want it to be prime, p must also be prime. But even then, you might still get a composite number. A French monk, Marin Mersenne, created a list of some of these. However, he got two wrong, and missed out three. It just so happens that there is a quicker way to tell whether a Mersenne number is prime so it is easier to generate big Mersenne primes.

Charlie: Why not try numbers of the form 2p+1?

Alex: Those are Fermat primes. They’re named after the French mathematician Pierre de Fermat. Carl Friedrich Gauss made an interesting discovery about them. It concerns constructions using only an unmarked ruler and a compass. Basically, an n-gon is constructible if and only if n is a power of 2 multiplied by some distinct Fermat primes. However, Fermat numbers are only prime if p is a power of 2 and even then only six Fermat primes are known. They are 2, 3, 5, 17, 257, and 65537.

Charlie: Here's another one. Take any even number above 2.

Simon: 20?

Charlie: Now express it as the sum of two primes.

Simon: 2 + 18 is no good. But 3 + 17 works.

Charlie: It’s probably possible for all even numbers above 2. But no one knows. I call it Goldbach’s Conjecture after Christian Goldbach who proposed it. He included 1 as a prime number but now that is no longer true. The modern version is stronger, since it excludes 1. Apparently no one knows how to prove it. But it is true for numbers up to about 4 * 1018. Another form is slightly weaker and says that every integer above 5 is the sum of three primes. A proof has been claimed but not verified. If the original is true, so is the weaker form. But if a bound is set, it can be proved or disproved by checking all numbers up to the bound. Since any search for a particular integer will terminate, it could finally be proved or disproved. But no known bound exists. And that’s not all. You can also try it with lucky numbers instead.

Alex: Also, why not try a lucky Ulam spiral? I would be intrigued to see any pattern.

 A small lucky Ulam spiral showing a tendency of lucky numbers to lie on diagonals. This was discovered by the author.
A small lucky Ulam spiral showing a tendency of lucky numbers to lie on diagonals. This was discovered by the author.

Charlie: Well, this really is a great pattern!

## Related entries

•Prime numbers