Primes and Perfect NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/