## 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. 2^{431126089}-1 is quite a big prime. They’ve
recently discovered an even bigger one. I think it was 2^{57885161}-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.
Charlie: Remember when you told us about large prime numbers? Why are
they all of the form 2^{p}-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 2^{p}+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
* 10^{18}. 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.
Charlie: Well, this really is a great pattern!## Related entries•Prime numbers | ||||||

Home • Contact |