home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10687 < prev    next >
Encoding:
Text File  |  1992-08-29  |  1.7 KB  |  50 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!nntp-server.caltech.edu!stieger
  3. From: stieger@cco.caltech.edu (Ronald David Stieger)
  4. Subject: Re: n doesnt divide 2^n-1
  5. Message-ID: <1992Aug28.223723.18851@cco.caltech.edu>
  6. Sender: news@cco.caltech.edu
  7. Nntp-Posting-Host: punisher
  8. Organization: California Institute of Technology, Pasadena
  9. References: <1992Aug28.194350.19717@cs.rose-hulman.edu>
  10. Date: Fri, 28 Aug 1992 22:37:23 GMT
  11. Lines: 37
  12.  
  13. goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard) writes:
  14.  
  15. >If someone could prove the following for me, I would be forever in 
  16. >his debt.
  17.  
  18. >If n > 1, then n doesnt divide 2^n-1.
  19.  
  20. >This _is_ a problem in a book, but I don't _DO_ homework anymore, I'm  
  21. >just curious.
  22.  
  23. OK. I had number theory spring term so let's see what I remember.
  24.  
  25. (1) a^p = a^q (mod m) iff p = q (mod t)
  26.       where t is the order (?) of m, that is the smallest positive 
  27.       number k (< m) s.t. a^k = 1 (mod m)
  28.  
  29. The proof of this fact is fairly straightforward.  p = q+rt so
  30.  a^p = a^(q+rt) = (a^q)*(a^(rt)).  a^(rt) = 1 (mod m) so a^p = a^q (mod m)
  31.  
  32. So... n divides 2^n - 1 implies 2^n = 1 = 2^0 (mod n) which implies by (1)
  33. n = 0 (mod t) so n divides t, the order of n.
  34.  
  35. Now, the order of n always divides n-1.  I don't remember how to prove this.
  36. Maybe you know, or someone else can post it, or maybe I'll think of it
  37. later.  You can test it if you like, a^(n-1) = 1 (mod n) for all a and n.
  38. So t divides n-1, but we also know that n divides t.  This 
  39. implies that n divides n-1, or n = 1 (mod n), which is only true if
  40. n = 1.
  41.  
  42. So, if n divides 2^n - 1, n = 1, and thus, as you asked,
  43.  
  44. if n > 1, n does not divide 2^n - 1.  QED.
  45.  
  46. -- 
  47. --Ron Stieger
  48.   stieger@cco.caltech.edu
  49. "Everybody wants a rock to wind a piece of string around."-They Might Be Giants
  50.