home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10410 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  2.4 KB
  1. Path: sparky!uunet!destroyer!sol.ctr.columbia.edu!usc!chaph.usc.edu!news
  2. From: rmurphy@aludra.usc.edu (Bob Murphy)
  3. Newsgroups: sci.math
  4. Subject: Re: u(v^n)w prime puzzle
  5. Date: 19 Aug 1992 13:56:16 -0700
  6. Organization: University of Southern California, Los Angeles, CA
  7. Lines: 50
  8. Message-ID: <l95dbgINN8t6@aludra.usc.edu>
  9. References: <l93702INNaq9@aludra.usc.edu> <1992Aug19.153755.14825@wri.com>
  10. NNTP-Posting-Host: aludra.usc.edu
  11.  
  12. In article <1992Aug19.153755.14825@wri.com> roach@bikini.wri.com (Kelly Roach) writes:
  13. >In article <l93702INNaq9@aludra.usc.edu> rmurphy@aludra.usc.edu (Bob  
  14. >Murphy) writes:
  15. BM>> If there were such values of u, v, and w, then one could construct
  16. BM>> arbitrarily large prime numbers.  Since I have often heard
  17. BM>> reference to "the largest known prime number", I would guess that
  18.                                ^^^^^ 
  19. BM>> there are no such values.  Now if only I had a proof.
  20.  
  21. KR>     Not quite.  The largest known prime number is 2^756839-1.
  22. KR>But emphasize the word "known" here. 
  23.  
  24. If you look carefully at my posting I said 'known'.  I am well aware
  25. that there is NO largest prime number.  I simply took the fact that a
  26. Mersenne number is the largest KNOWN prime and used it to GUESS that
  27. no such u,v,and w existed.  I specifically said that I don't have a
  28. proof.
  29.  
  30. KR>     There ARE infinitely many prime numbers and they do
  31. KR>get arbitrarily large.  A classic proof, due to Euclid is to
  32. KR>take
  33. KR>
  34. KR>     P = p1*p2*p3*...*pN+1
  35. KR>
  36. KR>where p1,p2,p3,...,pN are the primes you already know.
  37. KR>The number P is not divisible by any of p1,p2,p3,...,pN.
  38. KR>All the primes dividing P are new primes. 
  39.  
  40. Actually, Euclid's proof is slightly different than above.
  41.  
  42. Euclid's proof:
  43.  
  44. Suppose that p1 < p2 < ... < pn are all the primes.
  45. Let P = p1*p2*...*pn + 1 and let p be a prime dividing P;
  46. then p cannot be any of p1,p2,...,pn, otherwise p would divide
  47. the difference P - p1*p2*...*pn = 1, which is impossible.
  48. So this prime p is still another prime.
  49. This is a contradiction.
  50. Hence there are an infinite number of primes.
  51.  
  52.  
  53.                    Bob Murphy (rmurphy@aludra.usc.edu)
  54.  
  55.  
  56. p.s. For those interested, Euclid's proof can be found as 
  57.      Proposition 20 in Book IX of The Elements.  However, for a
  58.      more readable proof, I would suggest The Book Of Prime Number Records
  59.      by Paulo Ribenboim.  This book gives, as the author puts it,
  60.      9 and 1/2 proofs on the infinitude of primes.
  61.     
  62.