How to prove the following recursive sequence produce relatively prime numbers

Question

Sequence a_n is defined recursively:

$a_1 = 2$

$a_{n + 1} = {a_n}^2 - a_n + 1$

Prove that $a_i$ and $a_j$, $i \neq j$ are relatively prime.

Hint: Prove that $a_{n + 1} = a_1 a_2 \ldots a_n + 1$ and use Euclid’s theorem.

I came across this on Topcoder algorithm tutorial.I know the proof might be easy but I tried to solve it by creating more terms $ a_{n + 2}, a_{n + 3}$ by substituting $a_{n + 1}$ but that doesn't leads to proof.

Answer 1

For a simple proof, we bypass the hint.

Let $p$ be a prime that divides at least one $a_k$. Let $q$ be the smallest $k$ such that $p$ divides $a_k$. We show by induction on $n$ that $a_{q+n}\equiv 1\pmod{p}$. In particular, $p$ does not divide $a_{q+n}$. So any prime divides at most one of the $a_i$, which implies the $a_i$ are pairwise relatively prime.

Now to the induction proof. For the base case $n=1$, note that $a_{q+1}=a_q^2-a_q+1\equiv 0^2-0+1\pmod{p}$. And if $a_{q+n}\equiv 1\pmod{p}$, then $a_{q+n+1}\equiv 1^2-1+1=1\pmod{p}$.

Answer 2

We use part of the hint.

Using induction, it's a matter of making some substitutions and basic algebra to get that $$a_{n+1} = a_1\cdots a_n + 1.$$

Now, notice that it is enough to prove that given $n\in\Bbb N$, for each $1\leq k\lt n$, $a_k$ and $a_n$ are relatively prime. We proceed to do so.

For $1\leq j\lt n$ define $$\hat{a}_{n,j} = \frac{a_1\cdots a_n}{a_j}.$$

It's know that $$\gcd(a_n,a_j) = \min\{xa_n + ya_j : \text{$x,y\in \Bbb Z$ and $xa_n + ya_j\gt 0$}\}.$$

Pick $n\in\Bbb N$ and $1\leq j\lt n$. Since $$1=a_n - \hat{a}_{n-1,j} a_j\in \{xa_n + ya_j : x,y\in \Bbb Z\}$$ it should be that $\gcd(a_n,a_j) = 1$.

Answer 3

Hint $\ $ More generally, suppose we iterate $\,f(x),\,$ a polynomial with integer coefficents that further satisfies the conditions that $\,f(0) = 1 = f(1)\,\ \ $ [yours is $\,f(x) = x^2 - x + 1\,$]

${\rm mod}\ a_i\!:\,\ \color{#c00}{a_{i+1}} \equiv f(a_i) \ \,\equiv\,\ \, f(0) \equiv \color{#c00}1\,\Rightarrow\, (a_{i+1},a_i) = 1$

$\qquad\qquad \color{#0a0}{a_{i+2}} \equiv f(\color{#c00}{a_{i+1}}) \equiv f(\color{#c00}1) \equiv \color{#0a0}1\,\Rightarrow\, (a_{i+2},a_i) = 1$

$\qquad\qquad a_{i+3} \equiv f(\color{#0a0}{a_{i+2}}) \equiv f(\color{#0a0}1) \equiv 1\,\Rightarrow\, (a_{i+3},a_i) = 1$
$\qquad\qquad\qquad\ \vdots\qquad\qquad\qquad\qquad\qquad\qquad\vdots_{\phantom{I_{I_I}}}$
by using $\,\ a\equiv \bar a\, \Rightarrow\, f(a)\equiv f(\bar a),\,$ the Polynomial Congruence Rule.

So the gist is: $ $ iterating $f$ maps $\,0\,$ to the fixed point $1,\,$ universally coprime to any integer.