Prime Number Theorems

Date: 01/03/99 at 16:19:35
From: Alisa Levine
Subject: Prime Numbers

Hi. I have to write a math paper on prime numbers. I have a few 
questions. First of all, what exactly is the prime number theorem? Is 
there a way to provide a description in a simpler way to describe it? 
I know that it has to do with finding primes and proving primality. 
Also, what is the Lucas-Lehmer test for Mersenne primes, and how do 
Mersenne primes differ from other primes? What's the Riemann 
Hypothesis?

Thank you in advance for your time and your responses.
Alisa Levine

Date: 01/04/99 at 12:09:46
From: Doctor Wilkinson
Subject: Re: Prime Numbers

The Prime Number Theorem provides an approximate answer to the question 
"how many prime numbers are there between 1 and n?"  The answer is:

   "about n/ln(n)"

where ln(n) means the natural logarithm of n, which is the power you 
need to raise the number e to to get n.  (e is about 2.718281828).

A Mersenne prime is a prime of the form 2^n - 1. You can show by 
simple algebra that a number of this form can be prime only if n is 
also a prime. 

The Lucas-Lehmer test is a way of seeing whether a number of this 
form really is prime or not. All the really large primes that are 
known are Mersenne primes, because the Lucas-Lehmer test makes it easy 
(relatively speaking) to determine whether numbers of this form are 
prime or not. Nobody knows whether there is an infinite number of 
Mersenne primes. Currently 36 or 37 have been discovered. The test 
works as follows:

   You let p be a prime and let n = 2^p - 1. Let:

      S_1 = 4
      S_{k+1} = (S_k)^2 - 2 if k >= 1

   Then n is prime if and only if S_{p-1} is divisible by n.
                                   
Explaining the Riemann Hypothesis in simple terms is harder, because 
you need to know about infinite series and about complex numbers.  
This is about as simple as I know how to make it:

The function zeta(s), known as the Riemann Zeta Function, is defined 
for complex numbers s for which the real part of s is greater than 1, 
by the series:

   zeta(s) = sum(1/n^s)   n = 1, ..., infinity

The definition can be extended by a process known as analytic 
continuation to all complex values of s, except for s = 1. (We say 
that zeta(s) has a simple pole at s = 1). It is fairly easy to prove 
that zeta(s) is zero when s is a negative even number. The Riemann 
Hypotheses states that all the other zeroes of zeta(s) have imaginary 
part equal to 1/2. This is the most famous remaining unsolved problem 
in all of mathematics. Its importance for prime numbers is that if it 
is true, then we can estimate the number of primes between 1 and n 
more accurately.

- Doctor Wilkinson, The Math Forum
  http://mathforum.org/dr.math/