Prove that not all elements of this recurrent sequence are primes This  question  is a part of my assignment on elementary number theory and I am unable to solve it.

Let a, b and $x_0$ be positive integers and $x_n = ax_{n-1} +b $ for n=1, 2,...,... Prove that not all $x_n$ can be primes.

I tried by assuming that let all $x_n$ be primes. Then I can put $x_i$'s recursively to get a, b, $x_0$ but I am not able to find any contradiction based on that.
Can you please help?
 A: If $x_0$ is not prime, then there is nothing to prove.
If $a=1$, then $x_n=x_0 + n b$ and so is a multiple of $x_0$ for $n=x_0$.
If $a\ne1$, then
$$
x_n = x_0 a^n + b\frac{a^n-1}{a-1}
$$
and so $|x_n| \to \infty$ and $n \to \infty$.
If $x_n$ is always prime, then there is an $n$ such that $p=x_n$ does not divide $a$ or $a-1$. We can assume that $n=0$ by ignoring the previous terms. Then $a-1$ is invertible mod $p$. Moreover, if $m$ is a multiple of $p-1$, then $p$ divides $a^m-1$ and and so $p$ divides $x_m$, a contradiction.
A: In order for all the $x_n$'s to be prime, we must have $\gcd(a,b)=1$, in which case $\gcd(a,x_n)=1$ for all $n\ge1$. Now consider the sequence $x_1\to x_2\to x_3\to\cdots$ mod $x_1$. We get
$$0\to b\to(a+1)b\to(a^2+a+1)b\to\cdots\to(a^k+a^{k-1}+\cdots+a+1)b\to\cdots$$
To be precise, $x_n\equiv(a^{n-2}+a^{n-3}+\cdots+a+1)b$ mod $x_1$ for $n\ge2$. But it's easy to show, using Fermat's little theorem, that $a^k+a^{k-1}+\cdots+a+1\equiv0$ mod $x_1$ for some $k$: If $a\equiv1$ mod $x_1$ the sum is clearly $0$ mod $x_1$ for $k=x_1-1$, while otherwise we have
$$a^k+a^{k-1}+\cdots+a+1={a^{k+1}-1\over a-1}$$
for which the numerator is $0$ mod $x_1$ for $k=x_1-2$. To be precise again, we find that if $x_1$ is prime, then it divides $x_n$ for $n=x_1+1$ if $a\equiv1$ mod $x_1$ and $n=x_1$ if $a\not\equiv1$ mod $x_1$. And since we clearly have $x_1\lt x_2\lt x_3\lt\cdots$ since $a$, $b$ and $x_0$ are all positive integers, that $x_n$ cannot be prime.
A: First I'll make a change of variables, and say that $n=k+1$, this way you have $x_{k+1}=ax_k + b$. Now consider what happens when you apply the expression M-times, for example, if you apply it twice you get:
$$x_{k+2}=ax_{k+1}+b = a(ax_k + b) + b = a^2x_k + b(a+1)$$
$$x_{k+2}=a^2x_k + b(a+1)$$
And you if apply it three times you get:
$$x_{k+3}=a^3x_k + b(a^2+a+1)$$
Then you can generalize, and prove by induction, that if you use the expression to get the (k+M)-th number in terms of the k-th the result is:
$$x_{k+M}=a^Mx_k + b\sum_{i=0}^{M-1}{a^i}$$
Since the summation term is a geometric progression, you can substitute the closed formula for it:
$$\sum_{i=0}^{M-1}{a^i} = \frac{a^{M-1}-1}{a-1}$$
Which result in:
$$x_{k+M}=a^Mx_k + b(\frac{a^{M-1}-1}{a-1})$$
You can multiply the term $b(\frac{a^{M-1}-1}{a-1})$ by $\frac{a}{a}$.
$$x_{k+M}=a^Mx_k + b(\frac{a^{M}-a}{a(a-1)})$$
Fermat's little theorem states that if $p$ is a prime number and $a$ is an integer, than $a^p-a$ is an integer multiple of $p$. In the expression we found for $x_{k+M}$ we'll say that $M=x_k$, which will happen at some point in the sequence.
$$x_{k+M}=a^{x_k}x_k + b(\frac{a^{x_k}-a}{a(a-1)})$$
Since we have a $a^{x_k}-a$ and $x_k$ is prime, we can say that $a^{x_k}-a=Cx_k$ where $C$ a an integer.
$$x_{k+M}=a^{x_k}x_k + b(\frac{Cx_k}{a(a-1)})$$
Now we have a couple of possibilities. Since $b(\frac{Cx_k}{a(a-1)})$ has to be an integer, as it's just a sum of integers and $x_k$ is prime, then:

*

*$C$, or $b$ is a multiple of $a$, $a-1$ or both.

*$x_k$ is exactly equal to $a$ or $a-1$
If the second option is true, than we can just choose a different $x_k$ from the sequence, since it is all prime. Then choosing a $x_k$ that is not $a$ or $a-1$ (which can always be done) we have:

$$x_{k+M}=x_k[a^{x_k} + b(\frac{C}{a(a-1)})]$$
That would mean that $x_{k+M}$ is a multiple of $x_k$ which is a contradiction.
