home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10438 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.3 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!slc3.ins.cwru.edu!agate!dog.ee.lbl.gov!network.ucsd.edu!mvb.saic.com!unogate!beckman.com!dn66!a_rubin
  2. Newsgroups: sci.math
  3. Subject: Re: Can you prove it?
  4. Message-ID: <a_rubin.714325625@dn66>
  5. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  6. Date: 20 Aug 92 15:47:05 GMT
  7. References: <1992Aug20.055633.19046@nuscc.nus.sg>
  8. Keywords: Number theory
  9. Nntp-Posting-Host: dn66.dse.beckman.com
  10. Lines: 26
  11.  
  12. In <1992Aug20.055633.19046@nuscc.nus.sg> bhonsle@bhonsle.iss.nus.sg (Shailendra K Bhonsle) writes:
  13.  
  14. >Hi
  15. >I have a simple problem, can you prove or disprove it? I will appreciate all replies:
  16.  
  17. >Problem:
  18.  
  19. >Prove that for primes p & q, q<p
  20.  
  21. >if 2^(p-1) == 1 (mod q^2)
  22.  
  23. >then either 2^(q-1) == 1 (mod q^2) or q | p-1  { q divides (p-1}
  24.  
  25.  
  26. Actually, Bob's "proof" is wrong.  However, ....
  27.  
  28. 2^phi(q^2) == 1 (mod q^2), so (as phi(q^2) = q(q-1)), 
  29. 2^GCD(p-1,q(q-1)) == 1 (mod q^2).
  30.  
  31. If q does not divide p-1, then GCD(p-1,q(q-1)) = GCD(p-1,q-1) | q-1, so
  32. 2^(q-1) = 1 (mod q^2).
  33. --
  34. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  35. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  36. My opinions are my own, and do not represent those of my employer.
  37. My interaction with our news system is unstable; if you want to be sure I see a post, mail it.
  38.