# Proving any two elements in recursive sequence are coprime.

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.

• Note that all $x_i$ are odd. Oct 13 at 21:19

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.

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

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