home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10433 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.6 KB
  1. Path: sparky!uunet!seismo!darwin.sura.net!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!slc3.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
  2. From: bs@gauss.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.math
  4. Subject: Re: Can you prove it?
  5. Keywords: Number theory
  6. Message-ID: <1992Aug20.130921.3437@linus.mitre.org>
  7. Date: 20 Aug 92 13:09:21 GMT
  8. References: <1992Aug20.055633.19046@nuscc.nus.sg>
  9. Sender: news@linus.mitre.org (News Service)
  10. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  11. Lines: 37
  12. Nntp-Posting-Host: gauss.mitre.org
  13.  
  14. In article <1992Aug20.055633.19046@nuscc.nus.sg> 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 all replies:
  17. :
  18. :Problem:
  19. :
  20. :Prove that for primes p & q, q<p
  21. :
  22. :if 2^(p-1) == 1 (mod q^2)
  23. :
  24. :then either 2^(q-1) == 1 (mod q^2) or q | p-1  { q divides (p-1}
  25.  
  26. We have that 2 has order p-1 in the group of units of Z/q^2Z.
  27. Hence, p-1 | phi(q^2) by Lagrange's theorem.
  28.  
  29. Consequently, p-1 | q(q-1),  or  q(q-1) = k(p-1) for some integer k.
  30. Case 1.
  31.     k != q
  32.  
  33. We must have k | q-1,  hence  p-1 | q(q-1)/k  or  p-1 | q k'  for some
  34. integer k' and hence q | p-1 as required.
  35.  
  36. Case 2.
  37.     k = q.
  38.  
  39. Therefore p-q = q-1  and we have p=q. The first known case where 2^p-1 = 1 mod p^2  is p=1093. 
  40.  
  41. Since p =q in this case and we were given 2^(p-1) = 1 mod q^2, then we
  42. also have 2^(q-1) = 1 mod q^2.
  43.  
  44. QED
  45.  
  46. --
  47. Bob Silverman
  48. These are my opinions and not MITRE's.
  49. Mitre Corporation, Bedford, MA 01730
  50. "You can lead a horse's ass to knowledge, but you can't make him think"
  51.