3
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

The sequence $x_n \mod p$ will be periodic, and $x_n$ will be composite the next time $x_n \equiv 0 \mod p$.

$\endgroup$
  • $\begingroup$ What happens when $\alpha \equiv 0 \bmod p$ and $\beta=1$ ? $\endgroup$ – lhf Apr 6 '16 at 0:45
  • $\begingroup$ @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 :) $\endgroup$ – hugomg Apr 6 '16 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.