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. $
participants (4)
-
Frank Vernaillen -
Jeremy Cooper -
mpd@netcom.com -
pcw@access.digex.net