home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10482 < prev    next >
Encoding:
Text File  |  1992-08-21  |  2.5 KB  |  57 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!yktnews!victor
  3. From: victor@watson.ibm.com (Victor Miller)
  4. Subject: Re: Primes in x_{n+1} = ax_n+b (was Re: u(v^n)w prime puzzle)
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <VICTOR.92Aug21130002@terse4.watson.ibm.com>
  7. In-Reply-To: jeanmarc@ecrc.de's message of Fri, 21 Aug 1992 10:31:32 GMT
  8. Date: Fri, 21 Aug 1992 17:00:02 GMT
  9. Reply-To: victor@watson.ibm.com
  10. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  11. References: <a_rubin.714331997@dn66> <1992Aug21.103132.29967@ecrc.de>
  12. Nntp-Posting-Host: terse4.watson.ibm.com
  13. Organization: IBM, T.J. Watson Research Center
  14. Lines: 41
  15.  
  16. >>>>> On Fri, 21 Aug 1992 10:31:32 GMT, jeanmarc@ecrc.de (Jean-Marc Andreoli) said:
  17.  
  18. Jean-Marc> Let a,b be integers, and (x_n) be a sequence s.t. x_{n+1} = a x_n + b
  19.  
  20. Jean-Marc> My question is: does it contain infinitely many primes ?
  21.  
  22. Jean-Marc> There are trivial cases, where the answer is no:
  23. Jean-Marc> 1/ if (a x_0 + b = x_0) the sequence is constant.
  24. Jean-Marc> 2/ if (a = -1) the sequence alternates between two values x_0 and x_1.
  25. Jean-Marc> 3/ if ((a,b) > 1 or (x_0,b) > 1) then the sequence clearly
  26. Jean-Marc> contains only composite numbers.
  27.  
  28. Jean-Marc> What about the other cases ?
  29.  
  30. Jean-Marc> I've seen a "theorem of Dirichlet" in Hardy&Wright which
  31. Jean-Marc> handles the case a=1. Can anyone give me a pointer to a
  32. Jean-Marc> proof of that theorem (Hardy&Wright don't give it and the
  33. Jean-Marc> only reference they give is in German).
  34.  
  35. You can find proofs of Dirichlet's Theorem in lots of books on Number
  36. Theory.  If you just want to see elementary proofs of special cases,
  37. you could, for example, look in Riesel's book "The Book of Prime
  38. Number Records", Springer-Verlag, pp. 209ff.  There is a proof of the
  39. whole theorem, in Apostol's book "Analytic Number Theory", in
  40. Davenport and Montgomery's book "Multiplicative Number Theory" and
  41. scores of others.  Riesel also recommends Hasse's Vorlesungen ueber
  42. Zahlentheorie (now available in English Translation, Springer-Verlag).
  43.  
  44. The general question is certainly open.  For example, if x_0=1, a=2,
  45. b=1, then x_n = 2^n - 1.  In this case the question boils down to
  46. whether or not there are an infinite number of Mersenne Primes.  If
  47. you take x_0=2, a=2, b=-1, you get the same question about Fermat
  48. Primes.
  49.  
  50. Jean-Marc> ---
  51.  
  52. --
  53.             Victor S. Miller
  54.             Vnet and Bitnet:  VICTOR at WATSON
  55.             Internet: victor@watson.ibm.com
  56.             IBM, TJ Watson Research Center
  57.