Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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.

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search