# Show that each $a_n$ is divisible by a prime which does not appear in the factorization of any $a_i$, i<n

Consider the sequence of integers $a_n$ defined recursively by $a_n=a_{n-1}a_{n-2}...a_0 + 1$ with $a_0=1$. Show that each $a_n$ is divisible by a prime which does not appear in the factorization of any $a_i$, i

I was thinking of resembling it to Euclid's proof of infinitely many primes.

• Integers of the form $\,a = k a_i+1\,$ are coprime to $\,a_i\,$ since $\,\color{#0a0}a - k \color{#0a0}{a_i} = \color{#c00}1\,$ so $\,d\mid \color{#0a0}{a,a_i}\,\Rightarrow\,d\mid\color{#c00} 1.\$ This is essentially the same as Euclid's idea. – Bill Dubuque Mar 6 '15 at 21:07

it's exactly the same. since $a_n$ is not divisible by any of the prime factors of $a_1,\, a_2,\, \cdots ,\, a_{n-1}$, there must be a prime that does not appear in their factorization that divides $a_n$
Suppose $p$ divides $a_i$ for $i<n$. Then $a_n=bp+1$. So if $p$ divides $a$ then $p$ divides 1, a contradiction.