home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10955 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  1.2 KB
  1. Path: sparky!uunet!gatech!rutgers!igor.rutgers.edu!yoko.rutgers.edu!gore
  2. From: gore@yoko.rutgers.edu (Bittu)
  3. Newsgroups: sci.math
  4. Subject: Re: n doesnt divide 2^n-1
  5. Message-ID: <Sep.3.16.29.43.1992.1193@yoko.rutgers.edu>
  6. Date: 3 Sep 92 20:29:43 GMT
  7. References: <1992Aug28.194350.19717@cs.rose-hulman.edu> <1992Aug28.203144.13773@super.org>
  8. Organization: Hill Center
  9. Lines: 17
  10.  
  11. From kedlaya@b124.super.org (Kiran Sridhara Kedlaya) Fri Aug 28 16:31:44 1992
  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. But what if d = n? I don't see the contradiction in that case. Am I
  23. missing something? How does one show that d < n? There is probably a
  24. theorem that says that the order of 2 w.r.t an odd integer n is always
  25. less than n.
  26.  
  27. -Bittu
  28.