The Hunt For Primes

A Journey Through Their Mysteries and Mathematical Shortcuts

Prime numbers are among the most intriguing puzzles in mathematics — seemingly random yet deeply significant.

Their elusive pattern defies easy detection, making them both a source of fascination and frustration. The challenge grows exponentially with larger numbers, where determining if a number is prime becomes immensely time-consuming.

However, some clever shortcuts can speed up the search and help us swiftly eliminate impostors.

Before we can uncover the hidden mysteries behind prime numbers, we must first face the challenge of finding them…

Prime Numbers

We’ll start with a definition:

A prime number is a number with no factors except 1 and itself. Let’s clarify that a little:

We’re only concerned with positive integer numbers (so 3.5 and -4.19 can’t be primes)
We’re also only looking for positive integer factors
It’s important to note that 1 is not a prime. There are many reasons for this but we won’t get into that today.

If a number is not prime, we say that it is composite

Under this definition, 2, 3, 5, 7, 11, … are all primes, and all the even integers except 2 are composite (since they have a factor of 2).

With this in mind, let’s see if we can find some primes.

Checking Primality

A simple way to check if a number is prime would be to check every number smaller than it to see if it nicely divides our number. (Again, we’re just concerned with the positive integer factors here).

Is 53 Prime?

53 / 2 = 26.5,
53 / 3 = 17.6666…,
53 / 4 = 13.25,
…

Trying this out, it quickly becomes apparent that this will take a very long time especially if we want to check a particularly large number.

So what can we do to optimise this process? Well, there are 2 easy simplifications we can make.

Since factors come in pairs, there will always be one factor bigger than and one smaller than the square root of the number. Given we only need to find 1 factor to prove that a number is not prime, we only need to check values up to the square root.

If there is a factor higher than the square root, we will have already found its counterpart below.

The second optimisation we can make comes as a result of the Fundamental Theorem of Arithmetic.

This theorem states that:

“Every positive integer greater than 2 can be written as a product of prime factors.”

What this tells us, is that every number is either prime or can be expressed as a product of prime factors.

Therefore, we only need to check the known prime numbers to see if any of those are factors of our number.

(Any other composite factor would have a prime factor, which we’ve just checked for).

Putting these ideas together, it is sufficient to check only the prime numbers up to the square root when we are looking for factors.

So if we want to check if any number up to 10,000 is prime, we only need to check the prime numbers up to sqrt(10,000) = 100, of which there are only 25.

Example: Is 541 Prime?

sqrt(541) = 23.26

So we check the following primes for factors:

2, 3, 5, 7, 11, 13, 17, 19, 23

By observation, we can eliminate 2 and 5. A quick check of the remaining numbers tells us that 541 is indeed prime.

Non-Example: Is 493 Prime?

similarly to before, we start by finding the square root,

sqrt(493) = 22.2

So the primes we need to check are:

2, 3, 5, 7, 11, 13, 17, 19

again, we can eliminate 2 and 5 quite quickly, and a quick check shows that 17 is a factor:

493 = 17 * 29

So 493 is not a prime number.

(Notice that one factor is smaller than the square root, and one factor is larger).

Well, that’s certainly a lot easier than checking every single number!

Building New Primes

Sometimes mathematicians will need a huge prime number.

Checking for prime factors, even using a computer, could take a very long time. It also relies on us knowing all of the primes up to the square root. If we don’t have a complete list of primes, we might have missed a factor!

While it’s relatively easy to see if a number is prime, it’s much more challenging to find a list of all primes (up to a specific number).

But let’s say we do have a complete of primes, where we know that we have not missed any primes in between. How can we construct a new prime using this list?

Let’s introduce some notation:

Let p1, p2, …, pn be a complete list of primes.

Then we will construct a new number, q, as:

q = (p1 * p2 * … * pn ) + 1 (A product of existing primes, plus one)

So how does this help us find a new prime?

Well, there are 2 cases. Either:

q is prime and is not in our list of existing primes so we have found a new one, or
q is composite. In this case, q does not have any prime factors (from our existing list of primes) since if you divide it by any of p1, …, pn, then you will always get a remainder of 1. But since it is composite, it must have a prime factor, so there must be a new prime that is not on our list (we just don’t know what it is yet).

This method doesn’t guarantee we can explicitly know the new prime, but we do at least know that it’s there. We’ve at least narrowed down our search!

Let’s look at an example to illustrate this method:

Take a complete list of the first 3 primes: 2, 3, 5…
… multiply them together …
… and add 1,

= 31, which is indeed a prime.

It’s important to note that we can’t find every prime using this method — we may have found 31, but we’ve missed 11, 13, 17, …

[Note. This idea can be used to prove that there is an infinite number of primes since we can always construct a new one by taking a product of existing ones. This exercise is a great introduction to proof by contradiction].

Mersenne Numbers

A Mersenne Number is in the form 2ⁿ-1. The first 5 Mersenne numbers are:

2¹–1 = 1,
2²–1 = 3,
2³–1–7,
2⁴–1 = 15,
2⁵–1 = 31

A Mersenne Number that is also a prime is known as a Mersenne Prime. The first 3 Mersenne primes are 3, 7, 31.

You’ll notice that these numbers have a power of 2 that is also prime:

2²–1 = 3, and 2 is a prime
2³–1 = 7, and 3 is a prime
2⁵–1 = 31 and 5 is a prime

This a requirement for any Mersenne Prime: the index of the power of 2 must be a prime. However, the converse is not always true! It is not always the case that if the power is prime then we have a Mersenne Prime.

The Lucas-Lehmer Test

There is another way to check if a number is prime. It can only be used in a very specific case: checking if a Mersenne Number is a Mersenne Prime.

The following test for primality is known as the Lucas-Lehmer test.

Let’s take a Mersenne Number, m. We’ll assume that m is of the form

m = 2ᵖ-1

where p is a prime. So this is a potential prime number.

The test involves generating a sequence. We start with a₀ = 4, and recursively define: aₙ = aₙ₋₁² -2 (mod m)

[Note. The notation, “mod m” used here tells us that we need to divide the result by m and take the remainder as our answer.]

We define this sequence up until aₚ₋₂.

If aₚ₋₂= 0, then m is prime,
otherwise, m is composite.

Example: Is 8191 Prime?

2¹³ -1= 8191

a₀ = 4
a₁=14
a₂ = 194
a₃ = 37,634 = 4870
a₄ = 23,716,898 = 3953
a₅ = 5970
a₆ = 1857
a₇ = 36
a₈ = 1294
a₉ = 3470
a₁₀ = 128
a₁₁ = 0

Since this last term is zero, we know that 2¹³-1 is a Mersenne Prime.

Non-Example: Is 2¹¹-1 = 2047 Prime?

a₀ = 4
a₁=14
a₂ = 194
a₃ = 37634 = 788
a₄ = 620942 = 701
a₅ = 119
a₆ = 1877
a₇ = 240
a₈ = 282
a ₉= 1736

Since this last term is non-zero, we do not have a Mersenne Number.

Admittedly, for a large Mersenne Number, this process may still take a while, but it’s definitely still faster than checking possible factors.

Fortunately, in the case of Mersenne Primes, there are only 51 that we know to exist, so in fact, a quick Google search may be a faster method still!

The largest known Mersenne Prime is 2^(82,589,933) − 1, which of course means that 82,589,933 is a prime.

So there you have it: while prime numbers remain a mystery yet to be unraveled, finding and constructing them hopefully just became a little easier!

Thanks for reading 🙂

*Unless otherwise stated, all images are by the author.