# 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 $\displaystyle a,b,x_0$ be positive integers and define $\displaystyle x_n=ax_{n-1}+b \quad n=1,2,3,...$. Prove that not all the $\displaystyle x_n$ can be primes.

2. ## Re: Recursive sequence of primes

First assume (a,b)=1 else none of the $\displaystyle x_n$ are prime.
Try working out the general term $\displaystyle x_k$ in terms of a,b,k and $\displaystyle x_0$ only.
Suppose it is prime p say and consider the term $\displaystyle 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:

$\displaystyle 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 $\displaystyle 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, $\displaystyle x_k$, that is a prime p say. Then $\displaystyle x_{k+r(p-1)}\equiv 0 \pmod p$ for all r. This uses the fact that (a,b)=1 and $\displaystyle p\not| a$
So they can't all be primes.
(I believe that is enough to show they can't all be primes?)