home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11435 < prev    next >
Encoding:
Internet Message Format  |  1992-09-14  |  1.5 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: The Last Number Theory Problem
  5. Message-ID: <1992Sep14.211031.26379@infodev.cam.ac.uk>
  6. Date: 14 Sep 92 21:10:31 GMT
  7. References: <1992Sep14.134624.26925@cs.rose-hulman.edu>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 21
  11. Nntp-Posting-Host: apus.cus.cam.ac.uk
  12.  
  13. In article <1992Sep14.134624.26925@cs.rose-hulman.edu> goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard) writes:
  14.  
  15. >5.2.11.a (Solved) Show that if n is a pseudoprime to the base a but not
  16. >a pseudoprime to the base b, where (a,n)=(b,n)=1, then n is not a 
  17. >pseudoprime to the base ab.
  18. >
  19. >5.2.11.b Show that if there is an integer b with (b,n)=1 such that n is
  20. >not a pseudoprime to the base b, then n is a pseudoprime to <= \phi(n)
  21. >different bases a, with 1<=a<n.  (Hint: Show that the sets a_1, a_2,  
  22. >..., a_r, and ba_1, ba_2,...,ba_r have no common elements, where a_1,  
  23. >a_2, ..., a_r, are the bases less than n to which n is a pseudoprime.)
  24.  
  25. OK. The HINT is true: if n is pp to base a and not to base b then it is
  26. not pp to base ba.
  27. So, if "\phi(n)" be replaced by "{n\over2}" the result is true.
  28. (And clearly that's what was intended.)
  29.  
  30. The result stated does actually appear to be true, even in those cases
  31. -- 
  32. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  33. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  34.