From: Frank Vernaillen <Frank.Vernaillen@rug.ac.be>
Date: Mon, 11 Apr 94 11:57:27 PDT
To: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Subject: Re: Prime Numbers
In-Reply-To: <0heN1Dq00Vp=4P4EZX@andrew.cmu.edu>
Message-ID: <Pine.3.89.9404112055.A13985-0100000@eduserv>
MIME-Version: 1.0
Content-Type: text/plain




On Mon, 11 Apr 1994, Matthew J Ghio wrote:

> Well, for the mathematically curious, here are a few other interesting
> prime number theroms:
> 
> For any number n which is prime, (2^n)-1 is also prime (Mersenne's theorem).
> 
> For any number n (2^(2^n))+1 is prime. (I might have that wrong, I don't
> remember exactly)
> 
> For any number n, if the square root of (n!)+1 is an integer, it is also
> prime.  (This is interesting, but rather useless in practice)
> 

This is not "quite true"

1)   for (2^n)-1 to be prime, it is indeed necessary that n is prime
     (if n=pq then 2^p-1 divides 2^n-1)
     however (2^n)-1 is not prime for all prime n

     prime numbers of the form 2^n-1 are called Mersenne primes
     there are some 30 known Mersenne primes for the moment
     (could send interested people a list of the ones I know--see also 
     Knuth, volume 2 for some interesting stuff about primes)

2) (2^(2^n))+1 is certainly not true for all n, though I don't know
   any particularly values for which it doesn't hold (I thought
   2^128+1 was NOT a prime)

   primes numbers who happen to be of the form (2^(2^n))+1 are called 
   Fermat primes. Some pretty large ones are known (could send a list...)

3) I don't know about the third stated formula

Hope this straightens things out...

Frank.Vernaillen@rug.ac.be