Classic Math gone wrong...Re: (n!+1)^(1/2)

>  >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)
>
>For any number a, 1<a<=n, n! mod a == 0; therefore, n!+1 mod a == 1.  n!+1
>is prime.  Prime numbers don't have integral square roots.


You're getting things missed up with the classic proof that there is
no largest prime number. This doesn't hold in general. Try a=5. 
5!=5*4*3*2*1=120. 120+1=121. 121=11*11.

The classic proof goes:

Is there a largest prime number? 
If there is then collect all primes, p1...pn and multiply them
together p=p1*p2*...*pn. p+1 is not divisible by p1...pn. Therefore
p+1 is a prime. Therefore there is no largest prime number. 


 
>
>
>Scott Collins   | "That's not fair!"                         -- Sarah
>                | "You say that so often.  I wonder what your basis
>   408.862.0540 |  for comparison is."                 -- Goblin King
>................|....................................................
>BUSINESS.    fax:974.6094    R254(IL5-2N)    collins@newton.apple.com
>Apple Computer, Inc.  5 Infinite Loop, MS 305-2D  Cupertino, CA 95014
>.....................................................................
>PERSONAL.    408.257.1746       1024:669687       catalyst@netcom.com

> Scott Collins:
> (...) 
> The classic proof goes:
> 
> Is there a largest prime number? 
> If there is then collect all primes, p1...pn and multiply them
> together p=p1*p2*...*pn. p+1 is not divisible by p1...pn. Therefore
> p+1 is a prime. 

This last step (therefore p+1 is a prime) is not totally 
correct. You forgot the posibility p+1 NOT prime, but some prime 
number <p+1 but >pn divides p+1. This number is prime and >pn.
So in any case there would exist a prime >pn, which contradicts the
hypothesis, and the conclusion is indeed:

> Therefore there is no largest prime 
number.

Frank.Vernaillen@rug.ac.be

On Mon, 11 Apr 1994, Peter Wayner wrote:

> Is there a largest prime number? 
> If there is then collect all primes, p1...pn and multiply them
> together p=p1*p2*...*pn. p+1 is not divisible by p1...pn. Therefore
> p+1 is a prime. Therefore there is no largest prime number. 

That's cool, why doesn't anyone use this to generate large prime numbers?
I can see great potential for this one.  
 Awaiting scorching flames,
 Jeremy
                   _  .  _ ___ _  .  _
===-|)/\\/|V|/\/\ (_)/_\|_|\_/(_)/_\|_| Stop by for an excursion into the-===
===-|)||| | |\/\/  mud.crl.com 8888 (_) Virtual Bay Area!                -===

> On Mon, 11 Apr 1994, Peter Wayner wrote:
 
> > Is there a largest prime number? 
> > If there is then collect all primes, p1...pn and multiply them
> > together p=p1*p2*...*pn. p+1 is not divisible by p1...pn. Therefore
> > p+1 is a prime. Therefore there is no largest prime number. 
 
> That's cool, why doesn't anyone use this to generate large prime numbers?
> I can see great potential for this one.  
>  Awaiting scorching flames,
>  Jeremy

The product of a bunch of primes plus one is not necessarily prime.  It
just contains a prime factor not in the primes multiplied together.  When
looking for a large prime number in some range of integers, it is
computationally more efficient to simply strobe upwards from some starting
point testing for primality than it is to try to generate the prime
directly using a mathematical formula. 

-- 
     Mike Duvos         $    PGP 2.3a Public Key available    $
     mpd@netcom.com     $    via Finger.                      $