1
$\begingroup$

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.

$\endgroup$
13
  • 3
    $\begingroup$ This question should be asked on math.stackexchange.com. $\endgroup$
    – Nathaniel
    Apr 9 at 15:08
  • 2
    $\begingroup$ Asked there nobody helped asked here you didn't help $\endgroup$ Apr 9 at 15:10
  • 2
    $\begingroup$ Maybe you should have tried improving the question on math.SE according to the comments instead of asking it on another SE community… $\endgroup$
    – Nathaniel
    Apr 9 at 15:14
  • $\begingroup$ 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. $\endgroup$
    – awillia91
    Apr 9 at 15:44
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Apr 9 at 15:50
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ... $\endgroup$
    – plop
    Apr 9 at 23:19
  • $\begingroup$ ... 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$. $\endgroup$
    – plop
    Apr 9 at 23:30
0
$\begingroup$

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

$\endgroup$

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.