Генераторы взаимно простых

[Dave]

Последовательность $\{x_n\}_{n=1}^{\infty}$ начинается с $x_1=2$, а далее определяется по закону

1. $x_{n+1}=x_n^2-x_n+1$ ;
2. $x_{n+1}=x_n^2+x_n-1$ ;
3. $x_{n+1}=2^{x_n}-1$ .

Докажите, что все члены последовательности попарно взаимно просты.

[Sonic86]

a, b) $x_{n+1}=f(x_n)$
$x_{n+k}=f^k(x_n)$
$f^1(t)\equiv 1\pmod t \wedge$
$(y_k=f^k(t)\equiv 1\pmod t \Rightarrow f^{k+1}(t)=f(y_k)\equiv 1\pmod t)$
$\Rightarrow (\forall k)f^k(t)\equiv 1\pmod t$
$\gcd(x_{n+k},x_n)=\gcd(f^k(x_n),x_n)=\gcd(1,x_n)=1$
$x_1$ тут даже любой.

(Оффтоп)

c) Error: cannot allocate memory
А здесь от $x_1$ ответ зависит.

[Sonic86]

c. Поскольку $x_1=2$, то $\gcd(x_k,x_1)=1$.
$f(x):=2^{x}-1$
$\gcd(x_{n+k},x_n)=\gcd(2^{x_{n+k-1}}-1,2^{x_{n-1}}-1)=2^{\gcd(x_{n+k-1},x_{n-1})}-1=f(\gcd(x_{n+k-1},x_{n-1}))=...=f^k(\gcd(x_k,x_1))=f^k(1)=1$.
Видимо, в качестве $x_1$ можно взять как минимум любую степень двойки или любой член получающейся последовательности.