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
Best Answer
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.