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.


2 Answers 2


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.

  • $\begingroup$ so elegant. thank you. $\endgroup$
    – gournge
    Jan 6, 2021 at 15:19
  • $\begingroup$ You're welcome. $\endgroup$
    – Derek Luna
    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$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .