The Form of Primes

Two is the Oddest Prime

Two is the oddest prime number, since it is the only one that is even. All the other prime numbers must be odd. (This statement is the main idea underlying the Sieve of Eratosthenes, which is used to find all the prime numbers less than some given bound.) Thus, Euclid's proof that there are infinitely many prime numbers can be recast as a statement about the general form that a prime number can take. Euclid's result is equivalent to the following statements.

Theorem: There are infinitely many odd prime numbers.

Theorem: There are infinitely many primes of the form 2k + 1.

It is the last of these statements that I'd like to examine more carefully. Think about what happens when you try to divide an integer by 4. Sometimes it divides evenly, and sometimes there is a remainder. However, we can always reach the point where the remainder is one of the numbers 0, 1, 2, or 3. So, we can separate the integers into four piles, depending on the value of the remainder when you divide by 4. When we separate integers in this way, which of the piles gets the most prime numbers?

Fact: There are no prime numbers of the form 4k, because all of these numbers are divisible by 4.

Fact: There is only one prime number of the form 4k + 2; namely, the prime 2 that you get when n = 0. All the other numbers of this form are even.

So, the infinitely many odd primes get divided into two piles. Which pile gets infinitely many primes? Are there infinitely many primes of the form 4k +1? Are there infinitely many primes of the form 4k + 3?

Generalizing Euclid

The key step in Euclid's proof is to start with a finite list of primes, say

P₁ = 2, P₂, ..., P_M,

and then build new primes by factoring the number

N = P₁P₂...P_M + 1 = 2P₂...P_M + 1.

I have deliberately included the prime 2 explicitly, because it is now clear that the construction of N always produces odd numbers; i.e., numbers of the form 2k +1 . What would happen if we modified the definition of N so that we always produced numbers of some other form? More precisely, I'm going to ask you to make another decision.

• Suppose we always construct new numbers of the form 4k + 1 by taking N = 4P₂P₃...P_M + 1. Does this method work to construct infinitely many prime numbers of this form?
• Suppose we always construct new numbers of the form 4k + 3 by taking N = 4P₂P₃...P_M + 3. Does this method work to construct infinitely many prime numbers of this form?

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]