Prove that all members of a recursive sequence are coprime

Question

The problem is:

$k$ is a positive integer. Sequence $(a_n)$ is defined by: $$a_1=k+1 \\ a_{n+1}=a_n^2-a_n k + k. $$ Prove that every pair of members of that sequence is coprime.

By induction I got that $a_{n+1}=a_1 a_2 ... a_n + k $. A special case of that sequence is when $k=1$, it's called Sylvester's sequence. In that case, it's pretty easy to solve ($a_n\equiv 1\pmod b, b=a_m, m>n$ .) Otherwise, I'm completely stuck.

Answer 1

Let $m > n$. Suppose there exists a prime $p$ such that $p|a_{m}$ and $p |a_{n}$.

Then using your induction result, $p|a_{1}a_{2}\cdot\cdot\cdot a_{m-1}+k$, and $p|a_{1}a_{2}\cdot\cdot\cdot a_{n-1}+k$.

Hence, $p|(a_{1}a_{2}\cdot\cdot\cdot a_{m-1})-(a_{1}a_{2}\cdot\cdot\cdot a_{n-1})=(a_{1}a_{2}\cdot\cdot\cdot a_{n-1})(a_{n}a_{n+1}\cdot\cdot\cdot a_{m-1}-1)$.

If $p|(a_{1}a_{2}\cdot\cdot\cdot a_{n-1})$, then using the above, $p|k$ which implies for any $s$ that $p|a_{s+1} \implies p|a_{s}$ since $a_{s+1}=a_s^2-a_s k + k.$

By repeating this process, $p|a_{1} = k+1 \implies p|1$, a contradiction.

If $p|(a_{n}a_{n+1}\cdot\cdot\cdot a_{m-1}-1)$, then since $p|a_{n}, p|(a_{n}a_{n+1}\cdot\cdot\cdot a_{m-1}) \implies p|1$, a contradiction.

Hence there does not exist such a prime and all pairs are coprime.

Answer 2

This is reminiscent to the trick used by Euclid to prove the infinitude of primes. See, none of $a_1,\dots,a_n$ can divide $a_1a_2\cdots a_n+k$, because none of them divides $k$.