home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10683 < prev    next >
Encoding:
Text File  |  1992-08-29  |  3.1 KB  |  73 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!yale!gumby!destroyer!sol.ctr.columbia.edu!usenet.ucs.indiana.edu!newshost.cs.rose-hulman.edu!news
  3. From: goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard)
  4. Subject: n doesn't  divide .......
  5. Message-ID: <1992Aug28.230054.21269@cs.rose-hulman.edu>
  6. Sender: news@cs.rose-hulman.edu (The News Administrator)
  7. Nntp-Posting-Host: g214-1.nextwork.rose-hulman.edu
  8. Organization: Rose-Hulman Institute of Technology
  9. Date: Fri, 28 Aug 1992 23:00:54 GMT
  10. Lines: 61
  11.  
  12.  
  13. Allow me to nurse my ego a bit.  I have a Ph.D, in number theory. I  
  14. have taken on a project this summer, which is to produce a solution  
  15. manual for someone else's number theory book.  The book has 1235  
  16. problems.  I have worked 1214 of them so far, and TeXed them up.  I  
  17. posted one of the remaining 21 problems (to prove that n doesn't divide  
  18. 2^n-1) which I spent about 2 hours on and thought someone might help me  
  19. out a bit.  Thanks to Adam Logan and Keith Ramsay who gave concise  
  20. proofs. It's a big help for someone is has worked number theory  
  21. problems until he is nearly cross-eyed.  I intend to post a couple more  
  22. of these problems during the next week or so as I finish this project.   
  23. When I do, I would like to request that ALL ARROGANT ASSHOLES KEEP  
  24. THEIR BULLSHIT OUT OF MY MAILBOX.  
  25. Here a nice solution, appropriate to the level of the problem, given by
  26. Adam Logan:
  27. >If n is even, the result is trivial.
  28.  
  29. >Otherwise, letn be an exception, and let  p be the least prime  
  30. >dividing n. Since n > 1, such a prime exists.  By hypothesis, n | 2^n  
  31. >- 1, so p | 2^n - 1, i.e. 2^n == 1 (mod p).  Fermat proved that  
  32. >2^(p-1) == 1 (mod p). If gcd(n, p-1) = 1, we can choose a and b with  
  33. >an + b(p-1) = 1; then, raising the first equation to the power a, and  
  34. >the second to the power b, and multiplying, we get 2 == 1 (mod p),  
  35. >which is absurd.  Hence gcd(n, p-1) > 1, contradicting the minimality  
  36. >of p. (== means congruent to.)
  37.  
  38. >Similar but harder problem: prove that n^2 | 2^n + 1 iff n = 1 or 3.
  39. >(The description of numbers n s.t. n | 2^n + 1 is not so simple.)
  40.  
  41.  
  42. Here's a sample of the drivel I've been getting:
  43.  
  44. >     Sure.  Proof by extended example:
  45. >
  46. >          n=2,  2^n-1=3  -> n obviously does not divide 2^n-1 for n=2
  47. >          n=3,  2^n-1=8  -> n obviously does not divide 2^n-1 for n=3
  48. >          n=4,  2^n-1=15 -> n obviously does not divide 2^n-1 for n=4
  49. >          ...
  50. >     QED.
  51. >
  52. >     I'm sure that you can fill in the dots with all the time you have
  53. >     from not doing homework...
  54.  
  55. (har har har...You seem to have plenty of free time.)
  56.  
  57. >    Look up "Fermat's theorem" and the "Chinese remainder theorem"
  58. >    in any book on number theory.
  59.  
  60. (Big help.  Actually, one would have to strain oneself to use the CRT  
  61. on this problem.)
  62.  
  63. I have a head cold just now, and may regret my tirade later when I'm  
  64. not so grouchy, but I doubt it. 
  65.  
  66. Very, very sincerely,
  67. Bart
  68.  
  69. P.S.  If you meant your comments all in fun, and are surprised I took  
  70. offence, I sorry, I'm just not in the mood.  Further, keep any  
  71. apologies to yourself, I don't want to read it, just consider it  
  72. accepted.
  73.