home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10961 < prev    next >
Encoding:
Text File  |  1992-09-03  |  1.9 KB  |  43 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!hellgate.utah.edu!math.utah.edu!math-2-1.math.utah.edu!user
  3. From: gross@math.utah.edu (Fletcher Gross)
  4. Subject: Re: n doesnt divide 2^n-1
  5. Sender: news@math.utah.edu
  6. Date: Thu, 3 Sep 1992 21:48:07 GMT
  7. Organization: Math Dept, University of Utah
  8. References: <1992Aug28.194350.19717@cs.rose-hulman.edu> <1992Aug28.203144.13773@super.org> <Sep.3.16.29.43.1992.1193@yoko.rutgers.edu>
  9. Message-ID: <gross-030992154434@math-2-1.math.utah.edu>
  10. Followup-To: sci.math
  11. Lines: 30
  12.  
  13. In article <Sep.3.16.29.43.1992.1193@yoko.rutgers.edu>,
  14. gore@yoko.rutgers.edu (Bittu) wrote:
  15. > 
  16. > From kedlaya@b124.super.org (Kiran Sridhara Kedlaya) Fri Aug 28 16:31:44 1992
  17. > 
  18. > > Sure. Let n be the smallest integer > 1 such that n divides 2^n - 1.
  19. > > Let d be the smallest integer such that n divides 2^d - 1 (i.e. the order
  20. > > of 2, with respect to n). Then d divides n (otherwise n = rd + s, where
  21. > > 0 < s < d, and since 2^n and 2^d are congruent to 1 mod n, so is
  22. > > 2^(n - rd) = 2^s, whence n divides 2^s - 1, which is impossible
  23. > > by the choice of d). Also 2^d - 1 divides 2^n - 1, and d > 1 (otherwise
  24. > > n divides 2^1 - 1 = 1). So d is an integer > 1 but smaller than n, such
  25. > > that d divides 2^d - 1. Contradiction.
  26. > 
  27. > But what if d = n? I don't see the contradiction in that case. Am I
  28. > missing something? How does one show that d < n? There is probably a
  29. > theorem that says that the order of 2 w.r.t an odd integer n is always
  30. > less than n.
  31. > 
  32. > -Bittu
  33.  
  34. Since n divides 2^n - 1, n and 2 are relatively prime. If m is the Euler
  35. phi function of n, then n must divide 2^m - 1. Hence d <= m. Since m is the
  36. number of positive integers less than n and relatively prime to n, m <= n -
  37. 1. It follows that d < n.
  38.  
  39. Fletcher Gross                  |   (801) 581-6567
  40. Department of Mathematics       |   gross@math.utah.edu
  41. University of Utah              |
  42. Salt Lake City, Utah   84112    |
  43.