0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Note that all $x_i$ are odd. $\endgroup$ Oct 13 at 21:19
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.