home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10918 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  1.8 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!math.ksu.edu!deadend
  2. From: jxh@math.ksu.edu (James C. Hu)
  3. Newsgroups: sci.math
  4. Subject: Re: p prime, p divides ab => pdivides a or b
  5. Date: 3 Sep 1992 00:36:07 -0500
  6. Organization: Dept. of Mathematics, Kansas State University
  7. Lines: 32
  8. Message-ID: <184887INN7jp@hilbert.math.ksu.edu>
  9. References: <Btyo8q.E63@ux1.cso.uiuc.edu>
  10. NNTP-Posting-Host: hilbert.math.ksu.edu
  11.  
  12. Charles Blair (ceblair@ux1.cso.uiuc.edu) wrote:
  13. >   My recollection is that a number theory course I took presented
  14. >this as a difficult result, only proved after doing some stuff
  15. >with the Euclidean algorithm.  Is there a proof which avoids that?
  16.  
  17. I don't recall using the Euclidean algorithm, but the proof I had
  18. learned used a theorem we called Diophantine's Result:
  19.  
  20.     Let a, b be non-zero integers, where gcd(a,b)=d.
  21.     Then, there exists integers x,y such that
  22.     ax + by = d.
  23.  
  24. The proof to this is not hard, but it depends upon the Division
  25. Algorithm, which may be what you meant instead.  Using this, and the
  26. definition of a prime, it is quite easy to show that:
  27.  
  28.     p prime, then p | ab => p | a or p | b.
  29.  
  30. The proof basically assumes p does not divide either.  Then,
  31. gcd(p,a) = 1 and gcd(p,b) = 1.  We write down the Diophantine
  32. equations which are assured to exist, multiply them together, and
  33. arrive at an contradiction.
  34.  
  35. There are doubtless many other ways to prove this, but this result is
  36. required to prove UFT, and so I don't think any proofs of this using
  37. UFT would be wise.  (Of couse, prime decomposition may be enough alone
  38. to show the result)
  39. -- 
  40. James C. Hu (jxh@math.ksu.edu), 1804 Denholm Dr., Manhattan, KS 66502
  41. "If it was so, it might be; and if it were so, it would be; but as it
  42. isn't, it ain't.  Thats logic." - Lewis Carroll
  43. Opinions expressed are mine.  Let me know if they are someone else's.
  44.