Results 1 to 4 of 4

Math Help - Recursive sequence of primes

  1. #1
    Newbie
    Joined
    Jul 2011
    From
    .
    Posts
    17

    Recursive sequence of primes

    Hi,

    I've got this problem and have no idea how to start. Please, could anyone give me a hint?

    Let a,b,x_0 be positive integers and define x_n=ax_{n-1}+b \quad n=1,2,3,.... Prove that not all the x_n can be primes.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2010
    Posts
    4

    Re: Recursive sequence of primes

    First assume (a,b)=1 else none of the x_n are prime.
    Try working out the general term x_k in terms of a,b,k and x_0 only.
    Suppose it is prime p say and consider the term x_{k+p-1}.
    Hint: then use Euler-Fermat Thm (Apostol Thm 5.17 p.113)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    From
    .
    Posts
    17

    Re: Recursive sequence of primes

    Thanks for replying.

    Working out the general term I've seen it can be written this way:

    x_k=a^kx_0+b\displaystyle\sum_{i=0}^{k-1}a^i \quad\quad ^{**}

    I don't know if it's the more suitable for the exercise.

    Now, do you tell me to suppose p=^{**}? or, is p just a prime that is not related to the sequence?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2010
    Posts
    4

    Re: Recursive sequence of primes

    Yes so either they are all composite in which case we are done, or there is one, x_k, that is a prime p say. Then x_{k+r(p-1)}\equiv 0 \pmod p for all r. This uses the fact that (a,b)=1 and  p\not| a
    So they can't all be primes.
    (I believe that is enough to show they can't all be primes?)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Recursive sequence and primes
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: May 12th 2010, 07:14 PM
  2. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  3. recursive sequence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 29th 2009, 05:15 AM
  4. recursive sequence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 14th 2009, 06:33 AM
  5. recursive sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 5th 2008, 11:21 PM

Search Tags


/mathhelpforum @mathhelpforum