Primes and Perfect Numbers

Date: 08/08/97 at 13:34:25
From: Nick Younes
Subject: Primes and Perfects

Are there infinite numbers of prime and perfect numbers? Why? 

First of all, why is there an infinite number of numbers, period? 
Is it because there is an infinite number of numbers? If not, then 
why?

To say you cannot interchange the number of prime or perfect numbers 
with a variable "n", you would have to find a pattern that all prime 
or perfect numbers follow, such as a number of digits between two 
prime or perfect numbers. And this number would have to repeat only 
once for it to be considered a pattern. 

My question is, if  this is all a pretty big supercomputer has to do, 
why has no one yet written a program that analyzes the difference 
between the two number's in question?

I have heard of a formula that Fermat supossedly wrote that would 
allow him to instantly decide whether or not any given number was 
prime. Is there such a formula? If there is, than why is it not used 
instead of Cray IIa?
                 
Rather puzzled,
Erwin Schrodinger

Date: 08/14/97 at 12:14:19
From: Doctor Rob
Subject: Re: Primes and Perfects

There is an infinite number of prime numbers.  This was known to the
ancient Greeks.  

The proof goes something like this. Suppose to the contrary that there 
were only a finite number, which you could put into a list. Multiply 
them all together and add 1 to give a new number N. N is bigger than 
any number on the list, so it cannot be prime. On the other hand, it 
cannot be divisible by any number on the list either (if it were, that 
divisor would also divide 1, which is not possible). But N, like every 
number, can be written as a product of powers of prime numbers. This 
is a contradiction. Therefore any finite list of prime numbers is 
necessarily incomplete, and there must be infinitely many prime 
numbers.

Perfect numbers are more elusive.  They come in two flavors: odd and
even.

There is no known odd perfect number. If one exists, it must be very
large (more than 100 digits) and have lots of known special 
properties. It is conjectured that there are no odd perfect numbers, 
but no proof of that yet exists.

Leonhard Euler showed in the 18th century that even perfect numbers 
must have the form 2^(n-1)*(2^n - 1), and 2^n - 1 has to be prime.  
The numbers of the form 2^n - 1 are called Mersenne numbers. For a 
Mersenne number to be prime, it is necessary but not sufficient that 
n be a prime number. 

For example, if n = 2, 2^n - 1 = 3 is a Mersenne prime and 2*3 = 6 
is a perfect number. If n = 7, 2^n - 1 = 127 is a Mersenne prime and 
2^6*127 = 8128 is a perfect number, but if n = 11, 2^n - 1 = 2047 = 
23*89 is NOT a Mersenne prime, even though 11 is a prime.  

For more on Mersenne numbers and Mersenne primes, see the following:

  http://www.utm.edu/research/primes/mersenne.shtml   
   
For every Mersenne prime there is an even perfect number, and vice
versa. It is conjectured, but not proved, that there are infinitely
many Mersenne primes (and therefore infinitely many even perfect
numbers). The use of powerful computers to find new Mersenne primes 
has been going on since 1952. There is a wonderful test called the 
Lucas-Lehmer Test which allows a computer to prove or disprove the 
primality of Mersenne numbers, but it requires a lot of computation 
time and memory.

The pattern, if there is one, of differences between primes is not 
well understood by mathematicians. For example, it is not known 
whether or not there are infinitely many "twin primes," that is, 
primes which differ by 2, so that p and p+2 are both primes. Many 
examples have been found, but no proof that there are infinitely many, 
although this is believed to be true.

The pattern, if there is one, of differences between primes n such 
that2^n - 1 is a Mersenne prime, is also not understood.

As for Fermat's method of testing numbers, it is properly a 
compositeness test, not a primality test. To test N for compositeness, 
pick any number a less than N and bigger than 1. Compute the remainder 
upon division by N of a^(N-1). If this is anything but 1, the number 
is composite.  If this is 1, you cannot tell if the number is 
composite or prime.

This is not quite "instant", but it is fairly quick, especially on a
computer.  Unfortunately, it cannot prove primality, only disprove it 
in many cases.

Proving primality for large numbers other than Mersenne numbers is 
often very difficult.  That is why powerful computers are used.

I hope this answers your question.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/