Let $ T_n $ be the Chebychev polynomial of degree $ n $ which is defined for $ x $ in [-1,1] , by $T_n(x)=\cos\left(n\cdot \arccos{x}\right) $. In this case $ T_2(y)=2y^2-1 . $ Observe that \[ T_n\left(T_m(y)\right)=T_{nm}(y)=T_{m}\left(T_n(y)\right). \] In your case \[ a_{n+1}=T_2(a_n)= T_{2}\left(T_{2}(a_{n-1})\right)=T_{2^2}(a_{n-1})(x)=...=\] \[ =T_{2^j}(a_{n-j+1})=...=T_{2^{n+1}}(a_0)= ?? \] Note that another representation of $ T_n $ is $ T_n(t)=\frac{1}{2}\left( (t+\sqrt{t^2-1})^n+ (t-\sqrt{t^2-1})^n\right)\; ,\; t\in {\mathbb R}. $ However $ T_m(1)=1 .$ Therefore ... ? Perhaps help.

I'm under the impression that the problem has been posted before.

yeah, it's at least the third time it is posted. your number 2 is correct, it is particularly easy to prove knowing $a_n=\frac{1}{2} \left((2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\right)$. it helps with the original problem as well, when going from $F_p$ into $F_{p^2}$, so one has no problems with square roots. but the reason that one has to do this is sure the reason for not taking it as an IMO problem since the problem itself is beautiful. Peter

number 1 is correct as well if i'm not wrong. the proofs are not that hard. Peter

Um! Sorry if the orginal problem is old! Quote: number 1 is correct as well if i'm not wrong. the proofs are not that hard Really i see! Quote: your number 2 is correct, it is particularly easy to prove knowing....... . it helps with the original problem as well, when going from into , so one has no problems with square roots. but the reason that one has to do this is sure the reason for not taking it as an IMO problem since the problem itself is beautiful. Can u describe more details ? I just use something on $Z_p^*[\sqrt{3}]$ i think it helps!

it is correct that $gcd(n,a_n)=1$ We consider the $a_i$ modulo $p$.(p is prime) if one of $a_1,a_2,...,a_{p-1}$ is 0 or 1 modulo $p$ then $gcd(a_{kp},p)=1$. So one of the residues is came at least 2 times and because $a_i$ is alternating modulo $p$ so $gcd(a_n,p)=1$ for every $n$.So If $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ then $gcd(a_n,p_i)$=1 and problem is solved.

Oh if $p|a_n$ then $2^n+3|p^2-1$ and $p> \sqrt 2^{n+3}>n$ and problem is obvious.

I read the official solution, but it seems that yours is slightly different. Can you please post a detailed solution? Thank you very much

Before proceeding with the proof, we note that if $p | a_n$, then 2 is a quadratic residue modulo $p$. Indeed, since $p | a_n = 2a_{n-1}^2 - 1$, $\left(\frac{1}{a_{n-1}}\right)^2 \equiv 2 \pmod{p}$, so 2 is a quadratic residue modulo $p$. If $\theta = i \ln(2 + \sqrt{3})$, then $\cos \theta = 2$. We clearly have that \begin{align*} a_n &= \cos(2^n \theta) \\ &= \frac{e^{2^n \theta i} + e^{-2^n \theta i}}{2} \\ &= \frac{e^{2^n (i \ln(2 + \sqrt{3})) i} + e^{-2^n (i \ln(2 + \sqrt{3})) i}}{2} \\ &= \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2} \end{align*} We will now consider the sequence in $F_{p^2}$ (henceforth, all equalities will be taken in this field extension.) If $p | a_n$, we have that $(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n} = 0$. Since $\frac{2 + \sqrt{3}}{2 - \sqrt{3}} = (2 + \sqrt{3})^2$, we rearrange this to find that $(2 + \sqrt{3})^{2^{n+1}} = -1$. But $2 + \sqrt{3} = \frac{(1 + \sqrt{3})^2}{2}$; since 2 is a quadratic residue mod $p$, we have that there exists some $a$ such that $a^2 = 2 + \sqrt{3}$. Therefore, $a^{2^{n+2}} = -1$. Since $a^{2^{n+3}} = 1$, we must have that the order of $a$ in $F_{p^2}$ divides $2^{n+3}$, so it must be $2^k$ for some $k \leq n+3$. But if $k < n+3$, we may square the equality $2^{2^k} = 1$ a total of $n+2-k$ times to get that $2^{2^{n+2}} = 1 = -1$, which is a contradiction, so the order of $a$ is in fact $2^{n+3}$. By Lagrange's theorem, $a^{p^2 - 1} = 1$, so we have that $2^{n+3} | p^2 - 1$, as desired.

Zhero wrote: We will now consider the sequence in $F_{p^2}$ (henceforth, all equalities will be taken in this field extension.) If $p | a_n$, we have that $\color{red}{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n} = 0}$. By Lagrange's theorem, $\color{red}{a^{p^2 - 1} = 1}$, so we have that $2^{n+3} | p^2 - 1$, as desired. Sorry to revive, but can you tell me how you reached these? For the first one, that it holds on $F_p$ is clear but I'm not clear how it holds in $F_{p^2}$. For the second one, I don't think Lagrange's Theorem implies that.

The first conclusion follows from the fact that any element zero in $F_p$ is zero in $F_{p^2}$. The second follows from the fact that the $p^2 - 1$ nonzero elements of $F_{p^2}$ form a group under multiplication, so we may apply Lagrange's theorem accordingly. Keep in mind that $F_{p^2}$ is not the same as $\mathbb{Z}/p^2 \mathbb{Z}$; it is the finite field of order $p^2$, which contains all elements of the form $a + b\sqrt{c}$, where $a$ and $b$ are integers and $c$ is a quadratic non-residue mod $p$.

One can find out $a_n$ explicitly in terms of $n$ by defining the sequence of $<b_k>_{k \ge 0}$ by $a_k=\cosh b_k$ where $\cosh$ is the hyperbolic cosine defined by $\cosh x=\frac{e^x+e^{-x}}{2}$(By observing that $b_{k+1}=2b_k$.Then there is a bit of case study as when $(\frac{3}{p})=1$ and when $(\frac{3}{p})=-1$

In fact, working in $ F_{p^2} $ is only required if $ 3 $ is nonresidue modulo $ p $. If $ \sqrt{3} \in F_p $ then we can strengthen the claim to $ 2^{n + 3} \vert p - 1 $ using the same arguments as in Zhero's post. It is interesting to note that the trick of finding an $ a $ such that $ a^2 = 2 + \sqrt{3} $ can be motivated by the proof of a very similar problem. When proving that every prime factor $ p $ of a Fermat number $ 2^{2^n} + 1 $ satisfies $ p \equiv 1 \pmod{2^{n + 2}} $ this trick is also employed.

The hardest part of this problem the case when $\left(\frac{3}{p}\right)=-1$ Is there any way to do it without using Finite series and all that stuff. Here are some facts that may help $v_2(a_n-1)=2^{n+1}\forall n\ge 2$. By substituting $b_n=\frac{a_n-1}{2^{n+1}}$, I am getting a nice expression for $a_{n+1}$ in terms of $b_n$. dibyo_99 told me that this problem cannot be solved using the facts that I have found...but still if somebody's interested.. please try to solve the problem using these facts .

This proof is actually really similar to the proof of Lucas-Lhemer on finding Mersenne primes. We work in $\mathbb{F}_{p^2}$. First let $b_n=2a_n$. Then $b_n$ satisfies the recurrence $b_{n+1}=b_n^2-2$. Then take an element $x$ in $\mathbb{F}_{p^2}$ with $x+1/x=4=b_0$. Then $b_n=x^{2^n}+x^{-2^n}$. Since $b_n=0$ this means $x^{2^{n+1}}=-1$, so the order of $x$ is $2^{n+2}$. Unfortunately, this means $2^{n+2}\mid p^2-1$, so we want to strengthen this somehow. It would work to show $\sqrt{x}\in\mathbb{F}_{p^2}$. But note $x=2+a$ where $a^2=3$. Then $2+a=(1+a)^2/2$, so we want to show $2$ has a square root. But note $\left(\frac{2}{p}\right)=1$ if $8\mid p^2-1$. Since $n>0$ we have $8\mid 2^{n+2}\mid p^2-1$, so $x=2+a$ has a square root in $\mathbb{F}_{p^2}$, so the order of that square root is $2^{n+3}$ and we are done.

Nice problem! Here's my solution: Claim $1$: We have $a_n=\frac{(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}}{2}$. Proof: Note that $a_{n+1}=2a_n^2-1$ which is similar to the $\cos(2x)=2 \cos(x)^2-1$. This motivates us to choose a complex number $z$ such that $\cos z=2$(defining the $\cos$ function by the De Moivre formula for complex numbers that is) and then we have $\cos (2^n*z)=a_n$. Thus, if we can find a nice recursion for $\cos (2^n*z)$, say $b_n$, then we have $b_{2^n}=a_n$. Some work from here using trigonometric identities and De Moivre formula gives that $b_1=2, b_2=7, b_n=4b_{n-1}-b_{n-2}$ and thus $a_n=b_{2^n}$. Solving for closed form gives $b_n=\frac{(2+\sqrt{3})^n+(2-\sqrt{3})^n}{2}$ which proves our claim. Consider the sequence $c_n$ now, which is $c_1=1, c_2=4, c_n=4c_{n-1}-c_{n-2}$. First of all, note that $2b_nc_n=c_{2n}$ which comes from solving for the closed form of $c_n$ which is $c_n=\frac{(2+\sqrt{3})^n-(2-\sqrt{3})^n}{2}$. Now we make a bunch of algebraic manipulations. Note that $2^nc_n=\frac{(4+2\sqrt{3})^n-(4-2\sqrt{3})^n}{2}$. But note that $4+2\sqrt{3}=(1+\sqrt{3})^2$ and $4-2\sqrt{3}=(1-\sqrt{3})^2$. Which means that if we take a sequence $d_n$ with $d_1=1, d_2=2, d_{n+2}=2(d_{n-1}+d_n)$ then we have $d_{2k}=c_k*2^k$ by the closed form. This subtle manipulation will help us later, as we will see, also we can safely do it, as we are only concerned about the odd prime factors of $b_{2^k}=a_k$. Now, we will prove some lemmas. Lemma $1$: Define by $f(k)$ for a positive integer $k$ to be the largest positive odd factor of $k$. Then, we have $gcd(f(d_k),f(d_l))=f(d_{gcd(k,l)})$. Proof: Same idea as proving that for Fibonacci numbers $F_i$ we have $gcd(F_m,F_n)=F_{gcd(m,n)}$, just consider mod $n$ for any factor(which must be odd) $n$ of $gcd(f(d_k),f(d_l))$ and use Bezout lemma. We leave the detail since the rest is trivial. Lemma $2$: For any odd prime $p$, we have $p$ divides one of $d_p,d_{p-1},d_{p+1}$. Proof: Again similar to the proof for $F_n$, except this time we have $p|d_{p-{3|p}}$ where we use the Legendre symbol, analogous proof as for $p|F_{p-{5|p}}$, just some manipulations with the closed form. We omit details so as to not make the proof too long.

I showed a LTE-like result on $F_n$. We can apply a particular part of the proof exactly the same and show that: For any prime $p \neq 2,3$, if for some $n$ we have $p|d_n$ then we have, for all positive integers $k$: $v_p(d_{nk})=v_p(d_n)+v_p(k)$, and hence the same can also be said if $d_n$ is replaced by $c_n$ as $c_n*2^n=d_{2n}$. Note that the $p \neq 3$ condition doesn't affect our proof, and is safe, since mod $3$ check shows that $3$ never divides $b_{2^n}=a_n$ for any $n$. Corollary of lemma $3$( this is the main thing we are concerned with): If an odd prime $p$ divides $2^k*c_{k}=d_{2k}$(hence it divides $c_k$) for any $k$ and $v_2(k)=l$, then $p$ doesn't divide any number of the form $b_q$ with $v_2(q) \geq l$. Proof: We can see that there exists an odd number $r$ such that $p|c_{qr}$ and $p|b_q, b_q|b_{qr}$ by closed form thus $p|b_{qr}$. Now consider the LTE-ish result over $n=qr,k=2$ to get a contradiction. Conclusion: Hence, we get that if odd prime $p$ divides $d_{2m}$ and $v_2(m)=l$ then $p$ never divides any number of the form $b_{2^l*k}$. However we know that for $p \neq 3$( as $p=3$ doesn't matter since $3$ doesn't divide any $a_n$ anyway) we know from Lemma $2$ that $p$ divides one of $d_{p-1}, d_{p+1}$. Thus, if a prime $p$ divides $a_m=b_{2^m}$, and if $f(p)$ is the smallest positive number for which $p|d_{2f(p)}$, then we can see that $2^{m+1}|f(p)$ thus $2^{m+2}|2f(p)$. So one immediate necessary condition we get is that $2^{m+2}$ divides at least one of $p-1, p+1$. So we get that $p$ should be of the form $r*2^{m+2} \pm 1$ for some integer $r$, which translates to $2^{m+3}|p^2-1$. Thus we have proved that if an odd prime $p$ divides $b_{2^m}=a_m$ then we have $2^{m+3}|p^2-1$. Done.

Let $a_k=\frac{b_k+1/b_k}{2}$. The recursion becomes $b_{k+1}=b_k^2$, and we see that $b_0=2+\sqrt{3}$. Thus, \[a_n=\frac{1}{2}\left[(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\right].\]Suppose $p$ is an odd prime dividing $a_n$. First, note that $(1/a_k)^2\equiv 2\pmod{p}$, so $2$ is a square mod $p$. Now, we'll work in the field $K=\mathbb{F}_p[\sqrt{3}]$, which may be just $\mathbb{F}_p$, or may be $\mathbb{F}_{p^2}$. We see that \[a_n=0\iff\left(\frac{2+\sqrt{3}}{2-\sqrt{3}}\right)^{2^n}=-1.\]But, \[\frac{2+\sqrt{3}}{2-\sqrt{3}}=(2+\sqrt{3})^2=\left(\frac{(1+\sqrt{3})^2}{2}\right)^2=a^4\]for some $a$, since $2$ is a square in $K$. Thus, we have $a^{2^{n+2}}=-1$. Let $\ell$ be the order of $a$ in $K$. We see that $\ell\nmid 2^{n+2}$ but $\ell\mid 2^{n+2}$, so $\ell=2^{n+3}$. But we also know $\ell\mid|K^\times|\mid p^2-1$ by Lagrange's theorem, so $2^{n+3}\mid p^2-1$, as desired.

Here's an informal solution written to highlight motivation instead of rigor. Solved with eisirrational and goodbear. Let $b_n = 2a_n$, so $b_n = b_{n-1}^2 - 2$. The key is to note (in a massive abuse of notation that will be resolved later), that for a prime $p \mid a_n$: \begin{align*} a_{n-1}^2 - 2 &\equiv 0 \implies a_{n-1} \equiv \sqrt{2} \pmod{p}, \\ a_{n-2}^2 - 2 &\equiv \sqrt2 \implies a_{n-2} \equiv \sqrt{2+\sqrt{2}} \pmod{p},\\ \end{align*}and so on. So we need $\sqrt{2}, \sqrt{2+\sqrt{2}}, \dots$ to all exist modulo $p$, and moreover $\sqrt{2+\sqrt{2+\dots}} \equiv 4 \pmod{p}$ (where the LHS has $n$ twos). Let's rewind to make sure we are doing real math. Let $x_k = {2+\sqrt{2+\sqrt{2+\dots}}}$ with $k$ twos, which exists modulo $p$ if $x_{k-1}$ is a quadratic residue. It does not depend on the choice of square root we take, since it is true for $x_1 = 2$, and moreover $(2-\sqrt{x_{k}})(2+\sqrt{x_{k}}) = 4-x_{k} = 2 - \sqrt{x_{k-1}}$ is a QR (assuming $x_{k-1}$ is a QR) by induction so both factors are QRs or QNRs. The following is our main claim. Claim. The value $\sqrt{x_k}$ exists (i.e. $x_k$ exists and is a QR) and can equal $4$ (for some choice of square roots) only if $p \equiv \pm 1 \pmod{2^{k+2}}$. Proof. By induction, $x_k$ exists if and only if $p \equiv \pm 1 \pmod{2^{k+1}}$. We now check when it is a QR; we use two cases. Case 1: $-1$ is a QR. Then the number $\sqrt{x_k}/2 + \sqrt{4-x_k}/2 \cdot i = \operatorname{cis} \frac{\pi}{2^{k+1}}$ modulo $p$ exists and has order $2^{k+2}$. Thus, $2^{k+2} \mid p-1$. Case 2: $-1$ is not a QR. We do largely the same thing: we just work in $\mathbb{F}_p[i]$ or $\mathbb{F}_{p^2}$. Then the number $\sqrt{x_k}/2 + \sqrt{4-x_k}/2 \cdot i = \operatorname{cis} \frac{\pi}{2^{k+1}}$ now exists and still has order $2^{k+2}$, but is also equal to $2$ and is thus a QR in of itself. So $2^{k+3} \mid p^2 - 1$ and thus $p \equiv -1 \pmod{2^{k+2}}$. Yeehaw! $\square$ Using the claim, $p \mid a_k$ if and only if $x_n$ is a QR, i.e. $p \equiv \pm 1 \pmod{p}$ and thus $2^{k+3} \mid p^2 - 1$ as desired.

Define the sequence $b_n$ such that $a_n= \frac 12 \left( b_n+ \tfrac {1}{b_n} \right).$ Then the equation reads $b_{n+1}=b_n^2$ with $b_0=2+\sqrt 3$. Using this we have : $$ a_n = \frac 12 \left ( (2+\sqrt 3)^{2^n} + (2-\sqrt 3)^{2^n} \right)$$ We will work in $\mathbb F_p[\sqrt 3]$ which maybe $\mathbb F_p$ if $3$ is a QR mod $p$ and $\mathbb F_{p^2}$ otherwise. Note that if $\theta=2+\sqrt3$, we have : $$ a_n=0 \iff \theta^{2^n}+ \theta^{-2^n}=0 \iff \theta^{2^{n+2}}=1$$ Since $\mathbb F_p[\sqrt 3]^{\times}$ is cyclic, we have $2^{n+2} \vert p^2-1$. It boils down to proving that $\sqrt \theta$ exists in $\mathbb F_p[\sqrt 3]$ Note that : $$ \theta= 2+ \sqrt 3 = \frac 12 \left( 1+ \sqrt 3 \right)^2$$ So we need that $\left( \tfrac 2p \right)=1$ or equivalently $8\mid p^2-1$. However, we have $8 \mid 2^{n+2}\mid p^2-1$, so we are done.

Work in \(\mathbb F_{p^2}\), and let \(\omega=\frac{\sqrt6-\sqrt2}2\). Observe by Chebyshev that \[a_n=\cosh\left(2^n\cdot\cosh^{-1}2\right)=\frac{(2-\sqrt3)^{2^n}+(2+\sqrt3)^{2^n}}2=\frac{\omega^{2^{n+1}}+\omega^{-2^{n+1}}}2.\]It follows that \[a_n=0\iff\omega^{2^{n+1}}+\omega^{-2^{n+1}}=0\iff\omega^{2^{n+2}}=-1.\] This implies the order of \(\omega\) in \(\mathbb F_{p^2}\) is \(2^{n+3}\), i.e.\ \(2^{n+3}\mid p^2-1\).

I claim \[a_{n} = \frac{(2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}}}{2}\]We will prove this by inducktion. Our base case is $n = 0$, where we have \[a_{0} = \frac{(2+\sqrt{3})^{2^{0}} + (2-\sqrt{3})^{2^{0}}}{2} = \frac{2+\sqrt{3} + 2-\sqrt{3}}{2} = 2\]so our base case is proven. Onto our inducktive step. Assume this was true for $a_{n}$, we will prove this formula holds for $a_{n+1}$. We have \[a_{n+1} = 2a_{n}^{2} - 1 = \frac{((2+\sqrt{3})^{2^{n}})^{2} + ((2-\sqrt{3})^{2^{n}})^{2} + 2\cdot((2-\sqrt{3})(2+\sqrt{3})^{2^{n}}}{2} - 1\]\[= \frac{(2+\sqrt{3})^{2^{n+1}} + (2-\sqrt{3})^{2^{n+1}} + 2}{2} - 1 = \frac{(2+\sqrt{3})^{2^{n+1}} + (2-\sqrt{3})^{2^{n+1}}}{2}\]This proves our inducktive step, so our inducktion is complete. First, observe that \[2-\sqrt{3} = 2\cdot \left(\frac{1-\sqrt{3}}{2}\right)^{2}, 2+\sqrt{3} = 2\cdot\left(\frac{1 + \sqrt{3}}{2}\right)^{2}\] Now, consider some prime $p | a_{n}$. I claim $2$ is a QR modulo $p$. This is because since $p | a_{n} = 2a_{n-1}^{2} - 1$, it means \[\genfrac{(}{)}{}{}{\frac{p+1}{2}}{p}\genfrac{(}{)}{}{}{2}{p}= 1\Rightarrow \genfrac{(}{)}{}{}{2}{p} = 1\]Therefore, $2$ is a QR modulo $p$. Next, since $p$ is odd we must have \[p | (2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}} \Rightarrow p | \left(\frac{(1-\sqrt{3})^{2}}{2}\right)^{2^{n}} + \left(\frac{(1+\sqrt{3})^{2}}{2}\right)^{2^{n}} \]Again since $p$ is odd, we can ignore the factors of $2$ to get \[p | (1-\sqrt{3})^{2^{n+1}} + (1+\sqrt{3})^{2^{n+1}}\]If $3$ was a quadratic residue modulo $p$, then we can write $\sqrt{3}\equiv a\mod p$ to get \[(1-a)^{2^{n+1}} \equiv -(1+a)^{2^{n+1}} \Rightarrow \left(\frac{(1-a)}{1+a}\right)^{2^{n+1}} \equiv -1 \mod p\]Then, the order of $\frac{1-a}{1+a}$ must be $2^{n+2}$, so $p\equiv 1\mod 2^{n+2}$, which implies \[v_{2}(p^{2}-1) = v_{2}((p-1)(p+1)) = v_{2}(p-1) + v_{2}(p+1) \geq n+2 + 1 = n+3\]so $2^{n+3} | p^{2} - 1$. Otherwise, assume $3$ was not a QR modulo $p$. Consider the field \[\mathbb{F}_{p^{2}} = \mathbb{F}_{p}[\sqrt{3}] = \{a + b\sqrt{3} | a, b\in\mathbb{F}_{p}\}\]Then since $p | a_{n}$ we have \[(2+\sqrt{3})^{2^{n}} + (2-\sqrt{3})^{2^{n}} = 0 \Rightarrow \left(\frac{2+\sqrt{3}}{2-\sqrt{3}}\right)^{2^{n}} = -1\]\[\Rightarrow ((2+\sqrt{3})^{2})^{2^{n}} = -1 \Rightarrow \left(\frac{(1+\sqrt{3})^{2}}{2}\right)^{2^{n+1}} = -1\]Next, since $2$ is a QR modulo $p$, we can rewrite $2 = a^{2}$, and let $\frac{1+\sqrt{3}}{a} = c$. Now, we have \[(c^{2})^{2^{n+1}} = c^{2^{n+2}} = -1\]Therefore, the order of $c$ is $2^{n+3}$. It is well known that for any $x\neq 0$ in $\mathbb{F}_{p^{2}}$, we have $x^{p^{2} - 1} = 1$, thus $2^{n+3} | p^{2} - 1$, which is what we wanted to prove.

Note that \[a_i=\frac{(2+\sqrt{3})^{2^i}+(2-\sqrt{3})^{2^i}}{2}\]by an easy induction. Work in the field extension of $\mathbb F_p$ containing $\sqrt{3}$ for $p\mid a_n$. Then $(2+\sqrt{3})^{2^{n+1}}=-1$. This implies $(2+\sqrt{3})^{2^{n+2}}=1$ so $2^{n+2}\mid p-1$, implying the desired.

This problem has a very beautiful theoretical background. Let me first present and prove a theorem of Lucas and Lehmer, which has a striking resemblance with our problem. We will then see how, in fact, the two proofs are isomorphic. Theorem: Define the sequence $(t_i)_{i\geq 0}^{\infty}$ as $t_0=4$ and for $i\geq 1, \ t_i=t_{i-1}^2-2.$ Then, the $p^{th}$ Mersenne Number, $M_p:=2^p-1$ is prime if and only if $t_{p-2}\equiv 0\bmod{M_p}.$ This is also known as the Lucas–Lehmer primality test. Proof: We first want to find the general term of the sequence. Let $\omega=2+\sqrt{3}$ and $\overline{\omega}=2-\sqrt{3}.$ It follows by induction that $t_i=\omega^{2^i}+\overline{\omega}^{2^i}$ as such: \[t_{i-1}^2-2=\bigg(\omega^{2^{i-1}}+\overline{\omega}^{2^{i-1}}\bigg)^2-2=\omega^{2^{i}}+\overline{\omega}^{2^{i}}+2\big(\omega\overline{\omega}\big)^{2^{i-1}}-2=t_i.\]Assume that $t_{p-2}\equiv 0\bmod{M_p}.$ Therefore, for some positive integer $k,$ we have $\omega^{2^{p-2}}+\overline{\omega}^{2^{p-2}}=k\cdot M_p.$ By multiplying by $\omega^{2^{p-2}}$ we then get that $\omega^{2^{p-1}}+1=\omega^{2^{p-2}}\cdot kM_p.$ Assume that $M_p$ is composite and let $q$ be it's smallest prime factor. We will proceed to work in $\mathbb{Z}_q[\sqrt{3}].$ Observe that the inversable elements of $\mathbb{Z}_q[\sqrt{3}]$ form a group, $\mathbb{Z}_q^\times[\sqrt{3}]$ and because $0$ is an element with no inverse, then we have $$\big|\mathbb{Z}_q^\times[\sqrt{3}]\big|\leq \big|\mathbb{Z}_q[\sqrt{3}]\big|-1=q^2-1.$$Now, since $M_p\equiv 0\bmod{q}$ so $\omega^{2^{p-2}}\cdot k M_p=0$ which gives us $\omega^{2^{p-1}}=-1.$ Therefore, $\omega\in \mathbb{Z}_q^\times[\sqrt{3}]$ and its order is $2^p.$ However, the order of an element $g$ of a group $G$ is at most $|G|.$ This yields $2^p=\text{ord}(\omega)\leq\big|\mathbb{Z}_q^\times[\sqrt{3}]\big|\leq q^2-1.$ This is a contradiction, since $q$ is the smallest prime factor of $M_p,$ which is composite, so $q^2\leq M_p=2^p-1.$ Now, assume that $M_p$ is prime. Assume that $p>2$ yet again, to get that $M_p\equiv 7\bmod{12}$ and thus, $3$ is not a quadratic residue modulo $M_p$ but $2$ is a quadratic residue modulo $M_p.$ Then, by Euler's criterion, we get that \[3^{\frac{M_p-1}{2}}\equiv -1\pmod{M_p}\text{ and }2^{\frac{M_p-1}{2}}\equiv 1\pmod{M_p}.\]We'll continue working in $\mathbb{Z}_{M_p}.$ Now, by using the two latter congruences and the Binomial Theorem in a finite field, we get that \[(6+2\sqrt{3})^{M_p}= 6^{M_p}+(2\sqrt{3})^{M_p}=6-2\sqrt{3}.\]It now follows after a bunch of computations (we just use the 3 latter congruences) that \[\omega^{\frac{M_p+1}{2}}=\bigg(\frac{(6+2\sqrt{3})^2}{24}\bigg)^{\frac{M_p+1}{2}}=\frac{(6-2\sqrt{3})(6+2\sqrt{3})}{24}=-1.\]Finally, using the above evaluation of $\omega^{(M_p+1)/2}$ we can conclude that \[t_{p-2}=\omega^{2^{p-2}}+\overline{\omega}^{2^{p-2}}=\omega^{\frac{M_p+1}{4}}+\overline{\omega}^{\frac{M_p+1}{4}}=\overline{\omega}^{\frac{M_p+1}{4}}\big(\omega^{\frac{M_p+1}{2}}+1\big)=0.\]Hence, we proved both implication. The theorem is proven. Back to our problem, now that we have the LL Theorem in mind, observe that $a_i=t_i/2$ and thus we deduce that \[a_i=\frac{\omega^{2^i}+\overline{\omega}^{2^i}}{2}.\]Moreover, it follows naturally to work in $\mathbb{Z}_{p^2}^\times\cong\mathbb{Z}_p^\times[\sqrt{3}].$ As the numerous solutions above, we get that the order of $\omega$ is $2^{n+2}$ so $$2^{n+2}\mid |\mathbb{Z}_{p^2}^\times|=p(p-1)$$and thus, $2^{n+3}\mid p^2-1.$

pluricomplex wrote: The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\]Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$.

It is clear by induction that $$a_n=\frac{(2+\sqrt{3})^{2^n}+(2+\sqrt{3})^{-2^n}}{2^{n+1}}.$$Take some $p \mid a_n$ and work in $\mathbb{F}_{p^2}$. Since $2,\sqrt{3},\sqrt{2} \in \mathbb{F}_{p^2}$ and the last of these is nonzero, we can write $$2+\sqrt{3}=\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)^2,$$with the expression in parentheses being in $\mathbb{F}_{p^2}$ as well. Since $a_n=0$, we should have $$(2+\sqrt{3})^{2^n}+(2+\sqrt{3})^{-2^n}=0 \implies (2+\sqrt{3})^{2^{n+1}}=-1 \implies \mathrm{ord} (2+\sqrt{3})=2^{n+2} \implies \mathrm{ord} \left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)=2^{n+3},$$so by Lagrange we have $2^{n+3} \mid p^2-1$, as desired. $\blacksquare$

does this work? First notice $a_n\equiv 1\pmod 3$ for $n\ge 1$ so $p\ne 3.$ If $\left(\frac3p\right)=1$ then set $\alpha^2\equiv 3\pmod p,$ so $\alpha\not\equiv-2\pmod p$ and set \[a_0\equiv\frac12\left((2+\alpha)+\frac1{(2+\alpha)}\right)\pmod p.\]Then \[a_n\equiv\frac12\left((2+\alpha)^{2^n}+(2+\alpha)^{-2^n}\right)\pmod p.\]If this is $0$ then $(2+\alpha)^{2^n}\equiv -(2+\alpha)^{-2^n},$ so $(2+\alpha)^{2^{n+1}}\equiv-1\pmod p,$ and $(2+\alpha)^{2^{n+2}}\equiv 1\pmod p,$ so the order of $2+\alpha \pmod p$ divides $2^{n+2}$ but not $2^{n+1}$ so it is $2^{n+2}.$ Thus $2^{n+2}\mid p-1.$ Then $2\mid p+1$ so $2^{n+3}\mid p^2-1.$ If $\left(\frac3p\right)=-1$ then define $\alpha$ in $\mathbb F_{p^2}$ such that $a^2\equiv 3\pmod p.$ We can check for example by induction that $(2+\alpha)^m\not\equiv 0\pmod p$ for all positive integers $m.$ Similarly to before we have $(2+\alpha)$ has order $2^{n+2}\pmod p.$ Now consider $(2+\alpha)^{p+1}.$ We have \begin{align*}(2+\alpha)^{p+1}&\equiv(2+\alpha)(2+\alpha)^p\equiv (2+\alpha)(2^p+\alpha^p)\\&\equiv(2+\alpha)(2+\alpha\cdot3^{\frac{p-1}2})\equiv(2+\alpha)(2-\alpha)\equiv 1.\end{align*}Thus $2^{n+2}\mid p+1,$ and $2\mid p-1$ so $2^{n+3}\mid p^2-1.$

Using Chebychev Polynomials we conclude that $a_n=\frac{(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}}{2}$ for all $n \in \mathbb Z_{>0}$. We can as well get by the recursion formula that if $p \mid a_i$ for $p$ odd prime then $2$ is QR $\pmod p$. (This will help later, below actually lol) We will now work on the field extension $\mathbb F_{p^2}$ (in fact if $3$ is QR $\pmod p$ we can get $2^{n+3} \mid p-1$ by working entirely on $\mathbb F_p$ and not in the extension) $$a_n=0 \iff \left(\frac{2+\sqrt{3}}{2-\sqrt{3}} \right)^{2^n}=-1 \iff (2+\sqrt{3})^{2^{n+1}}=-1 \iff \left(\frac{(1+\sqrt{3})^2}{2} \right)^{2^{n+1}}=-1$$The last thing is a square $\pmod p$ so we can get some $a$ s.t. $a^{2^{n+2}}=-1$, which means $a^{2^{n+3}}=1$ so in fact $2^{n+3}$ is the order of $a$ in $\mathbb F_{p^2}$ so by Lagrange Theorem we get $2^{n+3} \mid p^2-1$ thus we are done .

First we define $T_N(X)$ as the $N^\text{th}$ Chebyshev Polynomial, as in \[T_N(\cos \theta)=\cos(N \theta)\]We also will use this. Lemma (Explicit representation of $T_N(X)$) We have \[T_N(X)=\frac12\left( \left(X+\sqrt{X^2-1} \right)^N+ \left(X-\sqrt{X^2-1} \right)^N \right)\]See that we have then \[a_n=T_{2^n}(2)=\frac12\left((2-\sqrt{3})^{2^n}+(2+\sqrt{3})^{2^n} \right)\]Now see that if $p=3$ then $3 \mid 2a_k^2-1 \iff a_k^2 \equiv 2 \pmod 3$ which is a contradiction. Hence assume $p \geq 5$. So we have \[p \mid \left((2-\sqrt{3})^{2^n}+(2+\sqrt{3})^{2^n} \right) \iff \left(\frac{2+\sqrt{3}}{2-\sqrt{3}} \right)^{2^n} \equiv -1 \iff (2+\sqrt{3})^{2^{n+1}} \equiv -1 \]Assume $n \geq 1$. Now we consider two cases. Case A: $\sqrt{3} \in \mathbb{F}_p$ This part is easy, just see that \[\text{ord}_p(2+\sqrt{3})=2^{n+2} \implies 2^{n+2} \mid p-1 \implies 2^{n+3} \mid p^2-1\]And done. Case B: $\sqrt{3} \not \in \mathbb{F}_p$ Here, considering a Frobenius endomorphism in $\mathbb{F}_{p^2}$ we get that \[\text{ord}_p(2+\sqrt{3})=2^{n+2} \implies 2^{n+2} \mid p^2-1\]Due to the fact that \[(2+\sqrt{3})^p=2-\sqrt{3} \text{ and } (2-\sqrt{3})^p=2+\sqrt{3}\]Assume $2^{n+3} \nmid p^2-1$. $\bullet$ If $\nu_2(p-1)=n+1$. Then see that \[(2+\sqrt{3})^{p-1} \equiv -1 \iff \frac{2-\sqrt{3}}{2+\sqrt{3}} \equiv -1 \iff 4 \equiv 0\]Contradiction. $\bullet$ If $\nu_2(p+1)=n+1$. Then see that \[(2+\sqrt{3})^{p+1} \equiv -1 \iff (2-\sqrt{3})(2+\sqrt{3}) \equiv -1 \iff 2 \equiv 0\]Contradiction, again.

learned this in Elias Caeiro's book on algebraic number theory, hope it works