# Prove that all members of a recursive sequence are coprime

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.

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.

• so elegant. thank you. Jan 6, 2021 at 15:19
• You're welcome. Jan 6, 2021 at 20:15

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

• could you clarify what does the bracket notation mean? it's just gcd(a, b), right? Jan 6, 2021 at 15:20
• yes, it's the gcd.
– user403337
Jan 6, 2021 at 18:38