home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11080 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  1.4 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!wupost!cs.utexas.edu!rutgers!igor.rutgers.edu!pepper.rutgers.edu!gore
  2. From: gore@pepper.rutgers.edu (Bittu)
  3. Newsgroups: sci.math
  4. Subject: Re: n doesnt divide 2^n-1
  5. Message-ID: <Sep.7.13.02.21.1992.5036@pepper.rutgers.edu>
  6. Date: 7 Sep 92 17:02:22 GMT
  7. References: <1992Aug28.194350.19717@cs.rose-hulman.edu> <1992Aug28.203144.13773@super.org> <Sep.3.16.29.43.1992.1193@yoko.rutgers.edu> <1992Sep4.152548.2904@super.org>
  8. Organization: Hill Center
  9. Lines: 24
  10.  
  11. In article <1992Sep4.152548.2904@super.org> kedlaya@metropolis.super.org (Kiran Sridhara Kedlaya) writes:
  12.  
  13. > Mea culpa. I forgot to mention that 2^phi(n) - 1 is divisible by n, and phi(n) 
  14. > is less than n, so d is at most phi(n), so it's less than n.
  15. > 
  16.  
  17. So we have at least two different proofs that 2^n is not congruent to
  18. 1 (mod n) for n > 1. While working on this problem I noticed a few
  19. things that are interesting. Since I still don't have any proofs, my
  20. observations are best summed up in the following conjecture:
  21.  
  22. Conj: For n >= 1, let 2^n = a.n + b where 0 <= b < n so that a is the
  23. quotient and b the remainder. Then the following hold:
  24.  
  25. 1. b is always even.
  26. 2. (even stronger) b is always a power of 2.
  27. 3. a is always even.
  28.  
  29. Note that 1 implies that n doesn't divide 2^n - 1 for n > 1. 2 gives
  30. us a slightly stronger theorem though I don't know how to say it. I
  31. don't know what 3 implies. My question is: Is any of the three
  32. statements true?
  33.  
  34. --Bittu
  35.