I'm working on a homework problem about finite automata and I got stuck trying to prove a fact about prime numbers that I think should be true.
Given a prime $p$ and integers $α$ and $β$, can I show that the sequence $x_0 = p; x_{n+1} = αx_n - β$ will contain at least one composite number? Assume that $α$ and $β$ are such that $x_n$ is always increasing.
I think it would be very surprising for this sequence to only contain prime numbers but I am very rusty on my number theory and would appreciate some hints on how to proceed.
The motivation for this question is that I am trying to use the pumping lemma to prove that the language of strings representing prime numbers in base 10 is not a regular language. The proof revolves around showing that for any sufficiently large prime $p$ and any decomposition of its decimal representation into three substrings $p = abc$ there will be at least one number in the sequence $abc$, $abbc$, $abbbc$, $...$ that is not prime. These subsequences can be represented as a linear recurrences $x_{n+1} = αx_n - β$ with an appropriate choice of $α$ and $β$.
For example, if I take the prime 1277 and the decomposition 1277 = 1 27 7 then we will have a sequence. 1277, 127277, 12727277, and so on. 1277 and 127277 are prime but 12727277 is not (its equal to 2143 x 5939)
The solution of the recurrence is $$ x_n = \alpha^n x_0 -\beta(1+\alpha+\cdots+\alpha^{n-1}) $$ Since $x_0=p$, we get $$ x_n \equiv -\beta(1+\alpha+\cdots+\alpha^{n-1}) \bmod p $$ If $\alpha \equiv 1 \bmod p$, then $$ x_n \equiv -\beta n \bmod p $$ and so $x_n \equiv 0 \bmod p$ for all $n$ that are multiples of $p$.
If $\alpha \not\equiv 1 \bmod p$, then $$ x_n \equiv -\beta\frac{\alpha^{n}-1}{\alpha-1} \bmod p $$ where the fraction is computed mod $p$.
If moreover $\alpha \not\equiv 0 \bmod p$, then $x_n \equiv 0 \bmod p$ for all $n$ that are multiples of $p-1$, by Fermat.
If $\alpha \equiv 0 \bmod p$, then $x_n \equiv -\beta \bmod p$, and the argument fails. But you've mentioned in a comment that this case cannot happen.