# Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$

Prove that there are infinitely many primes that divide none of the elements of the integer sequence $$a_{n+1} =1+a_0 a_1 \cdots a_n$$, with a starting point of $$a_0 \geq 0$$.

I thought about $$\log (x_n-1)=\log x_0x_1\cdots x_{n-1}= \log x_0 + \log x_1 +\cdots+\log x_{n-1}$$ to solve the problem but couldn't.

• This question should be asked on math.stackexchange.com. Apr 9 at 15:08
• Asked there nobody helped asked here you didn't help Apr 9 at 15:10
• Maybe you should have tried improving the question on math.SE according to the comments instead of asking it on another SE community… Apr 9 at 15:14
• Often problems like these are best by contradiction. Disclaimer: I haven't tried this problem myself yet, but my approach would be to assume there were finitely many primes that divide none of those elements, then there is a largest prime with that property, then I would try to find a larger one. Apr 9 at 15:44
• Seems easy if you don't look hard enough, but then it suddenly gets a lot harder. For a0 = 1, the sequence starts with 1, 2, 3, 7, 43, 1807, 1 + 1806*1807, and so on. The numbers grow rapidly (number of digits doubles every time), so the usual method "calculate a few values and see what happens" doesn't work. Apr 9 at 15:50

Let me write it here, because I had a typo in the comment.

First observe that \begin{align} a_{n+2}&=1+a_0a_1\dotsm a_na_{n+1}\\ &=1+a_0a_1\dotsm a_n(1+a_0a_1\dotsm a_n) \end{align}

So $$4a_{n+2}=(2a_0a_1\dotsm a_n+1)^2+3$$

This implies that for an odd prime $$p$$ that divides $$a_{n+2}$$, we must have that $$-3$$ is a quadratic residue modulo $$p$$. By quadratic reciprocity, $$-3$$ is a quadratic residue modulo $$p$$, when $$p$$ itself is a quadratic residue modulo $$3$$. Therefore, any odd prime of the form $$3K+2$$, with $$K\in\mathbb{Z}$$ doesn't have $$-3$$ as quadratic residue and cannot divide $$4a_{n+2}$$ for any $$n\geq0$$.

Since there are infinitely many primes of the form $$3K+2$$ (see here for example), then an infinite collection of primes that don't divide any of the elements of the sequence are the primes of the form $$3K+2$$, excluding from them $$2$$, the primes that divide $$a_0$$ and the primes that divide $$a_1$$.

Suppose that $$a_1 \cdots a_m \equiv 1 \pmod{p}$$ for some prime $$p$$, which in particular implies that $$p$$ doesn't divide $$a_1,\ldots,a_m$$. We claim that $$a_i \equiv a_{i \bmod m} \pmod{p}$$ for $$i > 0$$, where the modulo returns an answer in the range $$1,\ldots,m$$. We prove this by induction. This is clear when $$i \leq m$$. Now suppose it holds for all $$j < i$$. Let $$i-1 = dm + r$$, where $$0 \leq r < m$$. Then modulo $$p$$, \begin{align} a_i &= 1 + a_0 \cdots a_{i-1} \\ &\equiv 1 + a_0 (a_1 \cdots a_m)^d a_1 \cdots a_r \\ &\equiv 1 + a_0 a_1 \cdots a_r \\ &=a_{r+1}. \end{align}

It follows that if $$p$$ doesn't divide $$a_0$$, then it doesn't divide any element in the sequence.

It thus suffices to show that there are infinitely many primes that occur as factors of $$a_1 \cdots a_m - 1$$ (only finitely many can divide $$a_0$$).

Let us now assume that $$a_0 = 1$$, and so $$a_1 = 2$$. If $$p$$ is any prime divisor of $$a_1 \cdots a_m - 1$$ then $$a_1 \cdots a_{km+1} \equiv a_1 \not\equiv 1 \pmod{p}$$, since no prime can divide $$a_1 - 1 = 1$$.

In particular, this implies that a prime divisor of $$a_1 \cdots a_{a_j} - 1$$ cannot be a prime divisor of $$a_1 \cdots a_{a_{j+1}} - 1$$. It follows that there are infinitely many primes that occur as factors of $$a_1 \cdots a_m - 1$$.

I'm not quite sure how to handle larger $$a_0$$ at the moment.

• I think it can be finished the following way: Assume that $a_0=P^B$, where $P^B$ is a shorthand for a product of some primes to some positive exponents. Now, if $a_1a_2\dotsm a_m-1$ is divisible by primes not in $P$ we are in business. So, assume that $a_1\dotsm a_m-1=P^C$, with $C$ some tuple of non-negative exponents. We have that $a_1\dotsm a_{m+1}-1=a_1\dotsm a_m(a_0a_1\dotsm a_m+1)-1=(P^C+1)(P^B(P^C+1)+1)-1=P^{2C+B}+2P^{B+C}+P^B+P^C$. Now, let $q$ be a prime in $P$ and $b>0,c\geq0$ its exponents in $B,C$, respectively. We can factor out $q^{\min(b,c)}$, but ...
– plop
Apr 9 at 23:19
• ... the remaining factor is a multiple of $q$ plus either $1$ or $2$, depending on the case. The possibility of $q$ being $2$ needs to be studied separately but one can see an odd factor remaining. So, we can always find a $a_1\dotsm a_m-1$ that is divisible by some prime, that doesn't divide $a_1-1=a_0$.
– plop
Apr 9 at 23:30

We can prove that $$x^2+x+1$$ doesn't have any prime divisor of the form $$3n-1$$ and $$x_{n+1}=1+x_0x_1...x_n$$ so $$x_{n+1} = 1 +A$$ then $$x_{n+2} = A^2+A+1$$ and we are done because there are infinitely many $$3n-1$$ primes