# Thread: Recursive sequence of primes

1. ## 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.

2. ## 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)

3. ## Re: Recursive sequence of primes

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?

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?)