1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 6 '15 at 21:07
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

Suppose $p$ divides $a_i$ for $i<n$. Then $a_n=bp+1$. So if $p$ divides $a$ then $p$ divides 1, a contradiction.

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