Show that the greatest common divisor of any two terms in recursive sequence $T_{n+1} = T_n^2 - T_n + 1$ is 1.

Question

Question:

Consider the sequence of integers $T_n$ , where $n ∈ N$ defined by the recurrence relation $T_0 = 2$ , $T_{n+1} = T_n^2 - T_n + 1$ (for $n ∈ N$).

Show that for any $m$ , $n ∈ N$ with $m$ not equals to $n$, one has $\gcd(T_m , T_n) = 1$.

Answer: I show by induction that the statement P(n) : $T_n$=$T_0$$T_1$$T_2$...$T_{n-1}$ + 1 is true for n ≥ 1.

When n = 1,

$T_1$ = $T_0$ + 1 = 3.

Therefore, P(1) is true.

Assume P(k) is true for k ≥ 2.

To prove P(k+1) is true, i.e : $T_{k+1}$=$T_0$$T_1$$T_2$...$T_{k}$ + 1 .

RHS : $T_{k+1}$ = $T_n^2$ - $T_n$ + 1 = ($T_0$$T_1$$T_2$...$T_{k-1}$ + 1)^2 - ($T_0$$T_1$$T_2$...$T_{k-1}$ + 1) + 1 = $T_k^2$.

Answer 1

There are quite a few problems with what you’ve written. For starters, when $T_n=1$, $T_{n+1}=1^2-1+1=1$, not $0$. And any integer is divisible by $1$; no argument is required to justify that. And in fact $T_4=1807=13\cdot139$ is not prime.

HINT: $T_{n+1}=T_n^2-T_n+1=T_n(T_n-1)+1$, so $1=T_{n+1}-T_n(T_n-1)$. If $d\mid T_{n+1}$ and $d\mid T_n$, what does this equation tell you about $d$?

Answer 2

Let $m\lt n$. We show that $T_m$ and $T_n$ are relatively prime.

We show by induction on $i$ that in fact $T_{m+i}\equiv 1\pmod{T_m}$ for any $i\ge 1$.

The base case $i=1$ is obvious. And if $T_{m+i}\equiv 1\pmod{T_m}$, then $$T_{m+i+1}=T_{m+i}^2-T_{m+i}+1\equiv 1^2-1+1\equiv 1\pmod{T_m}.$$

Remark: Let $p_n$ be the smallest prime divisor of $T_n$. We have shown that if $m\ne n$ then $p_m\ne p_n$. It follows that there are infinitely many primes.

Answer 3

Prove by induction on $n$ that $$T_n=T_0T_1T_2\cdots T_{n-1}+1$$ for all $n$.

Namely, if $T_n=T_0T_1T_2\cdots T_{n-1}+1$, then $$T_{n+1}=T_n^2-T_n+1=(T_n-1)T_n+1=(T_0T_1T_2\cdots T_{n-1})T_n+1.$$

It follows that $T_m$ and $T_n$ are relatively prime when $m\ne n$. That's because, assuming $m\lt n$, any common divisor of $m$ and $n$ is also a divisor of $T_n-T_0T_1T_2\cdots T_{n-1}=1$.