Proving any two elements in recursive sequence are coprime.

Question

A sequence $x_0, x_1, x_2, \ldots$ is defined recursively as follows: $$x_0 = 3 \\ x_n = 2 + (x_0 \cdot x_1\cdot x_2\cdots x_{n-1})$$ I'm stuck at trying to prove that for any two different elements of the sequence, $x_i$ and $x_j$, it always holds that $x_i$ and $x_j$ are coprime.

Answer 1

Hint: apply the Euclidean algorithm to $x_i$ and $x_j$.

Answer 2

Suppose $i < j$ and $d|x_i$ and $d|x_j$.

Since $0 \le i \le j-1$, $x_j =2+\prod_{k=0}^{j-1}x_k =2+x_i\prod_{k=0, k\ne i}^{j-1}x_k $, $d | (x_j-x_i\prod_{k=0, k\ne i}^{j-1}x_k) =2$ so $d = 2$ or $d = 1$.

Since, as
John Omielan observed, all the $x_n$ are odd, $d=1$ so $x_i$ and $x_j$ are relatively prime.

Answer 3

Since $x_n = 2 + \prod_{k=0}^{n-1} x_k$,

$$\gcd(x_i, x_n) = \gcd\left(x_i, 2 + \prod_{k=0}^{n-1} x_k\right) = \gcd\left(x_i, 2 + x_i \prod_{k=0,k\neq i}^{n-1} x_k\right)$$

Now, if m is any integer, then $\gcd(a, b + m\cdot a) = \gcd(a, b)$.

$$\gcd(x_i, x_n) = \gcd\left(x_i, 2 + x_i \prod_{k=0,k\neq i}^{n-1} x_k\right)= \gcd\left(x_i, 2\right) = 1$$

The last equation is true because it should be obvious that all $x_i$ are odd(only because the first is though).