home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10930 < prev    next >
Encoding:
Text File  |  1992-09-03  |  1017 b   |  25 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!super!kedlaya
  3. From: kedlaya@b124.super.org (Kiran Sridhara Kedlaya)
  4. Subject: Re: n doesnt divide 2^n-1
  5. Message-ID: <1992Aug28.203144.13773@super.org>
  6. Sender: kedlaya@b124 (Kiran Sridhara Kedlaya)
  7. Nntp-Posting-Host: b124
  8. Organization: Supercomputing Research Center
  9. References:  <1992Aug28.194350.19717@cs.rose-hulman.edu>
  10. Date: Fri, 28 Aug 1992 20:31:44 GMT
  11. Lines: 12
  12.  
  13. Sure. Let n be the smallest integer > 1 such that n divides 2^n - 1.
  14. Let d be the smallest integer such that n divides 2^d - 1 (i.e. the order
  15. of 2, with respect to n). Then d divides n (otherwise n = rd + s, where
  16. 0 < s < d, and since 2^n and 2^d are congruent to 1 mod n, so is
  17. 2^(n - rd) = 2^s, whence n divides 2^s - 1, which is impossible
  18. by the choice of d). Also 2^d - 1 divides 2^n - 1, and d > 1 (otherwise
  19. n divides 2^1 - 1 = 1). So d is an integer > 1 but smaller than n, such
  20. that d divides 2^d - 1. Contradiction.
  21.  
  22. Kiran Kedlaya
  23. Supercomputing Research Center
  24. kedlaya@super.org (for the moment)
  25.