# How can I prove that a linear recurrence $x_{n+1} = αx_n - β$ will contain a composite number in the sequence?

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.
The sequence $x_n \mod p$ will be periodic, and $x_n$ will be composite the next time $x_n \equiv 0 \mod p$.
• What happens when $\alpha \equiv 0 \bmod p$ and $\beta=1$ ? – lhf Apr 6 '16 at 0:45
• @lhf: In my case $α$ is always a power of two so its never going to be a multiple of $p$. BTW, please don't tell Roberto that I came here :) – hugomg Apr 6 '16 at 0:54