home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10412 < prev    next >
Encoding:
Text File  |  1992-08-19  |  2.3 KB  |  80 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!wri!news
  3. From: roach@bikini.wri.com (Kelly Roach)
  4. Subject: Re: u(v^n)w prime puzzle
  5. Message-ID: <1992Aug19.221946.29768@wri.com>
  6. Sender: news@wri.com
  7. Nntp-Posting-Host: bikini.wri.com
  8. Organization: Wolfram Research, Inc.
  9. References: <1992Aug19.141957.17410@ecrc.de>
  10. Date: Wed, 19 Aug 1992 22:19:46 GMT
  11. Lines: 67
  12.  
  13. In article <1992Aug19.141957.17410@ecrc.de> jeanmarc@ecrc.de (Jean-Marc  
  14. Andreoli) writes:
  15. > Let x_n be the number u(v^n)w.
  16. > hence x_{n+1} - 10^r x_n = (vw - wz)
  17. > More generally, we have x_{n+1} = a x_n + b
  18. > and we have to prove that such a sequence is either constant or
  19. > contains at least one composite, for any integral values of
  20. > x_0,a,b (with a>1).
  21. > ...
  22. > QED
  23.  
  24.  
  25.      Looks like you've got it.  Not the proof I had in mind,
  26. but still, I think it is correct.  Perhaps I'll still post my
  27. solution Friday so that others understand what I was hinting
  28. at.
  29.  
  30.  
  31.  
  32. > Now, I propose the following question:
  33. > 
  34. > Is it true that any sequence x_{n+1} = a x_n + b is either
  35. >constant or contains *infinitely many* composite ? *almost
  36. >only* composite (i.e. it contains only a finite number of primes) ?
  37.  
  38.  
  39.       I think I can answer the first question quickly.
  40. I will just dismiss the cases a=-1,0,1 to the readers.
  41. Certainly, x_0=1 with x_{n+1}=-x_n is pretty boring.
  42. Also, we may suppose (a,b)=1 since (a,b)!=1 is not
  43. interesting.  My restriction |a|>1 makes |x_n|<=1 for
  44. all n impossible.  If necessary drop some of the first
  45. few terms of {x_i} and renumber the sequence so that we
  46. have |x_0|>1 and also (x_0,a)=1.  The latter relation is
  47. trivial to achieve because (a,b)=1.  If you doubt I
  48. can make |x_0|>1, note |a|>1 and see (2) below.
  49.      Since |x_0|>1 and also (x_0,a)=1, I can pick a
  50. prime p such that
  51.  
  52. (1)  p | x_0     and      p does not divide a
  53.  
  54. We see by the difference equation x_{n+1} = a x_n + b
  55. that
  56.  
  57. (2)  x_n = a^n*x_0 + b*Sum[a^i,{i,0,n-1}]
  58.  
  59. Now this Sum is a geometric series and by (1)
  60.  
  61.      a^i (mod p)
  62.  
  63. is a periodic function in i.  You can read my solution
  64. to the u(v^n)w puzzle on Friday to find out that
  65.  
  66. (3)  Sum[a^i,{i,0,n-1}] = 0 (mod p)     if p(p-1) | n.
  67.  
  68. or prove it yourself.  Hence, by (1), (2), and (3), we
  69. have
  70.  
  71. (4)  p | x_n     if p(p-1) | n
  72.  
  73. By |a|>1 and (2), it is clear that |x_n| -> infinity,
  74. so it follows by (4) that infinitely many of the x_n
  75. are composite. 
  76.  
  77.  
  78.  
  79.  
  80.