Prove that $x_n$ and $n$ are coprimes

Question

I'm here again with a problem of Italian National Math Olympiads 2007. Given the following subcession:

Given the following succession

$$\left\{\begin{matrix} x_1=2\\ x_{n+1}=2x_n^2-1 \end{matrix}\right.$$

Prove that $\gcd(x_n,n)=1 \ \ \ \forall n> 1$

My attempt

I thought that maybe, having the close formula for $x_n$ could simplify the problem. I noticed the the recursion formula is analogous to the cosine duplication formula:

$$\cos(2x)=2\cos^2(x)-1$$

So basically at each iteration step we are duplicating the cosine and:

$$x_n=\cos(2^{n-1}\arccos(x_1))=\cos(2^{n-1}\arccos(2))$$

Calculating $\arccos(2)$ is equivalent to this equation:

$$\cos(x)=2$$ $$\frac{e^{ix}+e^{-ix}}{2}=2$$

Substituting $e^{ix}=t$:

$$t+\frac 1t=4$$ $$t^2-4t+1=0$$ $$t=2\pm \sqrt{3}$$ $$e^{ix}=2\pm \sqrt{3}$$ $$x=\frac{\ln(2\pm \sqrt{3})}{i}$$

So:

$$x_n=\cos\left(2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}\right) $$

By Euler's formula:

$$x_n=\frac{e^{i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}+e^{-i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}}{2}$$ $$x_n=\frac{(2\pm \sqrt{3})^{2^{n-1}}+(2\pm \sqrt{3})^{-2^{n-1}}}{2}$$

The signs can be determined by checking some values. In the end: $$x_n=\frac{(2+\sqrt{3})^{2^{n-1}}+(2+ \sqrt{3})^{-2^{n-1}}}{2}$$ $$x_n=\frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2}$$

So now we have to proof that if $p|n$ then $p \nmid \frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2} $ with $p\in \Bbb{P} $. If $p=2$ the proof is trivial because clearly $x_n \equiv 1 \pmod{2} \ \ \ \ \forall n\geq 2$ . So we can limitate us to study the simplified expression:

$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}$$

Then I don't know how to continue :(

I tried using Newton binomial we obtain:

$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}= \sum_{i=0}^{2^{n-1}} {2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}+\sum_{i=0}^{2^{n-1}} (-1)^i{2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}$$

Notice that if $i\equiv 1 \pmod{2}$ the terms get simplified so:

$$\sum_{i=0}^{2^{n-2}} {2^{n-1}\choose 2i} 3^{i} 2^{2^{n-1}-2i+1} $$

But then I can't see the pattern :(

Can you help me, I would like to know how to solve this problem and if possible how to continue my solution.

Thank you for your time

Answer 1

The idea is to study the sequence $x_n$, $n\in\mathbb N$, of the question modulo all primes $p$ and to show that $x_n$ cannot be zero mod $p$ if $n\geq p$. This implies that $x_n$ and $n$ are coprime because $x_n$ is coprime to all primes $p\leq n$.

I will work in the ring of integers modulo some prime $p$ and use the notation $\bar z$ for the residue class modulo $p$, that is $\bar z=z+p\mathbb Z$. Recall that $\bar z\pm\bar y=\overline{z+y},\ \bar z\cdot\bar y=\overline{z\cdot y}$.

If $p=2$ then $\overline{x_{n+1}}=\overline{2x_n^2-1}=\overline{-1}=\bar 1$ for all $n=1,\dots$ by the recursion. Hence $x_n$ is odd for $n\geq2$.

If $p=3$ then $\overline{x_2}=\bar 7=\bar 1$ and it follows by induction that $\overline{x_n}=\bar 1$ for all $n\geq2$: This is true for $n=2$. If it is true for some $n$, then we have $\overline{x_{n+1}}=\bar 2(\overline{x_n})^2-\bar1=\bar2\bar1^2-\bar1=\bar1$.

$\newcommand{\Z}{{\mathbb Z}}$ If $p\geq5$, $p=2m+1$, then consider the set $S=\{\overline{2y^2-1}|y\in\{0,1,\dots m\}\}$ of cardinality $\leq m+1$. Consider also the operator $T:\Z/p\Z\to\Z/p\Z$ defined by $T(\bar z)=\bar 2(\bar z)^2-\bar1$. By induction, we have $\overline{x_n}=T^{n-1}(\bar 2)$ for $n=1,2,\dots$. Now for every element $\bar z\in\Z/p\Z$, we have $\bar z\in\{\bar0,\bar1\dots,\bar m\}$ or $-\bar z\in\{\bar0,\bar1\dots,\bar m\}$. Hence every image $T(\bar z)=\bar 2(\bar z)^2-\bar1=\bar 2(-\bar z)^2-\bar1$ of $T$ is an element of $S$.

In particular the $m+2$ terms $\overline{x_2},...,\overline{x_{m+3}}$ are all in $S$ which has at most $m+1$ elements. Hence at least two of them must be equal, say $\overline{x_{j}}=\overline{x_{j+r}}$, where $2\leq j<j+r\leq m+3$. By induction using $\overline{x_{n+1}}=T\overline{x_{n}}$, we conclude that $\overline{x_{k}}=\overline{x_{k+r}}$ for all $k\geq j$: The subsequence $\overline{x_{n}}$, $n\geq j$, is $r$-periodic.

Claim: None of the terms $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ equals $\bar0$.

Proof: Otherwise, $\overline{x_{j+r}}$ would be an image $T(\bar0)$ or an image $T^s(\bar0)$ for some integer $s\geq2$. By the definition of $T$, we would have $\overline{x_{j+r}}\in\{-\bar1,\bar1\}$ and hence $\overline{x_{j}}=\overline{x_{j+r}}\in\{\bar1,-\bar1\}$. This would lead to $\overline{x_{j+r}}=T^r(\overline{x_{j}})=\bar 1$ and hence to $\overline{x_{j}}=\bar 1$. This in turn would imply that $\overline{x_{j}}=\overline{x_{j+1}}=\cdots=\overline{x_{j+r-1}}=\bar1$ contradicting the assumption that one of the terms $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ equals $\bar 0$.

The above Claim and the $r$-periodicity of the subsequence $\overline{x_{n}}$, $n\geq j$, imply that $\overline{x_{n}}\neq\bar0$ for all $n\geq j$. Since $j<j+r\leq m+3\leq2m+1=p$, we conclude that $\overline{x_{n}}\neq\bar0$ for $n\geq p$ as we wanted to show.

Answer 2

Assume, on contrary that there exists a prime number $p>3$ (the cases $p=2,3$ are trivial) such that $p\mid n$ and $p\mid x_n$. Let $t_1=2+\sqrt 3\in\Bbb F_p[\sqrt 3]$, $t_n=t_1^{2^{n-1}}$. Then $x_n\bmod p=(t_n+t_n^{-1})/2$, consequently, $t_1^{2^n}=t_n^2=-1$ in $\Bbb F_p[\sqrt 3]$. Let $g$ be a generator of the multiplicative group of $\Bbb F_p[\sqrt 3]$ and let $m\in\Bbb Z$ such that $t_1=g^m$.

If $\Bbb F_p[\sqrt 3]=\Bbb F_p$, then $g$ has order $p-1$, hence $g^{m2^n}=g^{(p-1)/2}$ implies $2^nm\equiv\frac{p-1}2\pmod{p-1}$, from which $2^p\mid 2^{n+1}\mid (p-1)$, a contradiction.

If $\Bbb F_p[\sqrt 3]\neq\Bbb F_p$, then $g$ has order $p^2-1$, hence $g^{m2^n}=g^{(p^2-1)/2}$ implies $2^nm\equiv\frac{p^2-1}2\pmod{p^2-1}$, from which $2^p\mid 2^{n+1}\mid (p^2-1)$, a contradiction.