Prime Numbers
Introduction
A prime number is an integer that has exactly
two factors. These numbers include 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, .... There are infinitely many of these, as can be proven in a variety of
ways. Here is one fascinating way to do this. As shown on the theorems page,
the harmonic series 
diverges to
infinity. Now we use this to prove that there are infinitely many prime
numbers. First we make the bold statement: 
. How can we make such a statement? Well, we note that every
integer greater than 1 can be written as the product of primes, so it follows
that 
. Conveniently, each of the parentheses encloses a geometric
series that we can sum, so we get 
. Thus we reach the infinite product above. If there are only
a finite number of primes, then the right side will not diverge, but we already
know that the left side will, so we have a contradiction, so there must be an
infinite number of primes. Obviously, there are simpler ways of proving this,
but I believe that this method gives the most insight into the distribution of
primes.
More on the Distribution of the Primes
Let us define
a function 
to be the number
of prime numbers not exceeding x. Thus 
because 2, 3, 5,and 7 are primes. Also, 
(count them!).
But what can be said about other numbers? Is there a general method of
determining 
for some random value for x? Since the distribution of primes
seems to be random, it seems that the answer to this question would be
"no." Indeed, there is no known function that gives an exact value of
. However, we can get an approximation. Gauss, as a fifteen-year-old
boy, conjectured the following limit: 
. Here is a graph of the function 
:
.
What this means is that the number of primes increases over time, but in general more gradually. Thus there are more primes in the range 1 to 10 000 000 than there are in the range 10 000 000 to 20 000 000, for example. This theorem was proven by Tchebyshev using complex analysis sometime during the 19th century. It was not until 1952 that Erdös and Selberg finally proved this theorem without complex numbers. This theorem is so important in number theory that we call it the Prime Number Theorem.
Another thing we know about the
distribution of prime numbers is called Bertrand's Postulate. This postulate states
that for every integer n > 1, there is at least one prime such that 
. This inequality has been sharpened lately, and we now know
that 
for n sufficiently large.
Perfect Squares, Modulo 4, and the Two Types of Primes
With the exception of 2, all
primes are odd numbers. Naturally, odd numbers can be classified: are they one
more than a multiple of four, or are they one less than a multiple of four? If
they are one more than a multiple of four, they are congruent to 1 (mod 4). If
they are one less than a multiple of four, they are congruent to 3 (mod 4).
If we have a
prime that is congruent to 1 (mod 4), it can be written as the sum of two
perfect squares in exactly one way. If it is congruent to 3 (mod 4), it cannot
be written as the sum of two perfect squares in any ways.
We know that there are an
infinite number of primes in each of these two categories. Mostly, it is these
two categories that set apart different classes of primes.
Mersenne Primes
A Mersenne prime is a prime
in the form 
, where p is a positive integer. This expression may or may
not be prime. However, we do know that p must be a prime if the expression is
going to be a prime. All Mersenne primes are in the category of primes that are
congruent to 3 (mod 4). We do not know whether there is an infinite number of
them.
Fermat Primes
A Fermat prime
is a prime in the form 
. Fermat conjectured that all numbers in this form would be
prime. And as far as he could hope to check by hand, it was true. For 
, he was right. However, when we let n=5, we get 
. We have now checked all values of n up to 24, and we have
not found another prime yet. Thus we have now conjectured the reverse: there
are no more Fermat primes.
Sophie Germain Primes
A pair of
Sophie Germain primes is a set of two prime numbers p and 2p+1. p can be either
1 (mod 4) or 3 (mod 4), but 2p+1 must be 3 (mod 4). These primes were invented
along the bumpy path to prove Fermat's Last Theorem. Sophie Germain was the
first person to attempt a general proof of Fermat's Last Theorem, rather than
proving it for individual prime exponents. We do not know if there is an infinite
number of Sophie Germain primes.
Twin Primes
A pair of twin primes is a set of two primes that differ by two. They must always be centered around a multiple of six, with the exception of 3 and 5. A set of twin primes must contain one prime congruent to 1 (mod 4) and one prime congruent to 3 (mod 4). The product of a set of twin primes is congruent to 8 (mod 9) except for 3 and 5. It is unknown whether there is an infinite number of twin primes.