home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10878 < prev    next >
Encoding:
Text File  |  1992-09-02  |  1.3 KB  |  32 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!utcsri!skule.ecf!rairan
  3. From: rairan@ecf.toronto.edu (RAI Ranjan)
  4. Subject: Re: p prime, p divides ab => pdivides a or b
  5. Message-ID: <BtyqL2.9A8@ecf.toronto.edu>
  6. Keywords: Contrapositive
  7. Organization: University of Toronto, Engineering Computing Facility
  8. References: <Btyo8q.E63@ux1.cso.uiuc.edu>
  9. Date: Wed, 2 Sep 1992 18:12:37 GMT
  10. Lines: 20
  11.  
  12. In article <Btyo8q.E63@ux1.cso.uiuc.edu> ceblair@ux1.cso.uiuc.edu (Charles Blair) writes:
  13. >
  14. >   My recollection is that a number theory course I took presented
  15. >this as a difficult result, only proved after doing some stuff
  16. >with the Euclidean algorithm.  Is there a proof which avoids that?
  17.  
  18.   Contrapositive is a fancy way of saying reductio ad absurdum :)
  19.  
  20.   It basically means that for any propositional statements s and t:
  21.                     s => t <=>  not(t) => not(s)
  22.   So to prove p|(ab) => p|a or p|b, we just show that if p does not 
  23. divide a AND p does not divide b, then p does not divide ab.  By the
  24. Fundamental Theorem of Arithmetic this is obvious.  Euclid's algorithm is
  25. not necessary.  Indeed, the proof of the extended Euclidean algorithm
  26. depends on this result, I think.
  27. -- 
  28. ---
  29. Ranjan Rai                             <rairan@ecf.toronto.edu> 
  30. Engineering Science 9T3                <rairan@eecg.toronto.edu>
  31. University of Toronto                      
  32.