home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10457 < prev    next >
Encoding:
Text File  |  1992-08-20  |  1.3 KB  |  62 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!wri!news
  3. From: roach@bikini.wri.com (Kelly Roach)
  4. Subject: Re: Can you prove it?
  5. Message-ID: <1992Aug20.210400.1773@wri.com>
  6. Sender: news@wri.com
  7. Nntp-Posting-Host: bikini.wri.com
  8. Organization: Wolfram Research, Inc.
  9. References: <1992Aug20.055633.19046@nuscc.nus.sg>
  10. Date: Thu, 20 Aug 1992 21:04:00 GMT
  11. Lines: 49
  12.  
  13. In article <1992Aug20.055633.19046@nuscc.nus.sg>  
  14. bhonsle@bhonsle.iss.nus.sg (Shailendra K Bhonsle) writes:
  15. > Hi
  16. > I have a simple problem, can you prove or disprove it? I will appreciate  
  17. all replies:
  18. > 
  19. > Problem:
  20. > 
  21. > Prove that for primes p & q, q<p
  22. > 
  23. > if 2^(p-1) == 1 (mod q^2)
  24. > 
  25. > then either 2^(q-1) == 1 (mod q^2) or q | p-1  { q divides (p-1}
  26.  
  27.  
  28.      The case q=2 is trivial, so suppose q is odd.  Let
  29.  
  30.      ord(2,q^2) == minimum x>0 such that 2^x==1 (mod q^2)
  31.  
  32. By elementary number theory,
  33.  
  34. (1)  ord(2,q^2) | phi(q^2) == q(q-1)
  35.  
  36. where phi() is the Euler phi function.  Now suppose
  37.  
  38.      2^(p-1) == 1 (mod q^2)
  39.      2^(q-1) != 1 (mod q^2)
  40.  
  41. These equations give us
  42.  
  43. (2)  ord(2,q^2) | p-1
  44. (3)  ord(2,q^2) does not divide (q-1)
  45.  
  46. Putting (1) and (3) together we get
  47.  
  48. (4)  q | ord(2,q^2)
  49.  
  50. Putting (2) and (4) together we get q | p-1.
  51.  
  52.                 QED
  53.  
  54.  
  55.       We need q prime to get (4).  We didn't really
  56. need p to be prime nor q<p for the proof to work.  We
  57. just need p to be odd (for the trivial case q=2).
  58.  
  59.  
  60.  
  61.  
  62.