Number theory with sequences The sequence $x_0,x_1,x_2,x_3,x_4,.....$ is defined as:
\begin{cases}
x_0 = 2 \\
x_k =2\cdot x_{k-1}^2-1 &\text{for every }k>0\\
\end{cases}
Prove that if an odd prime number $p$ divides $x_n$, then $2^{n+3}$ divides $p^2-1$

My idea was to firstly treat simple cases like this:
If $n=0$, then $x_0=2$ doesn't have any odd divisors.
If $n=1$, then $x_1=7$. It has only one odd prime divisor, $7$ and $2^{n+3}=2^4=16$ divides $p^2-1=7^2-1=48$
.........
From here, my idea was to apply some sort of induction but induction doesn't work too well with prime numbers so this is where I got stuck with this idea.
Another idea was to write $x_n$ in its polynomial form and making it easier to prove what we want. I think that induction might work here but I still didn't manage to do it. Can you help me, please?
 A: The general solution to the recursion is:
$$x_n = \frac{\alpha^{2^n} + \alpha^{-2^n}}{2}$$
Which can be shown by induction.
By the initial condition, we get $\alpha = 2 + \sqrt3$. Then:
$$x_n = \frac{(2 + \sqrt3)^{2^n} + (2 - \sqrt3)^{2^n}}{2}$$
Now things start to become weird. If you expand both terms in parenthesis, you can eliminate square roots because they are negative in the second expansion. Take a prime that divides this integer and use $r$ as an integer square root of 3 in the modulus p. I still can't prove it exists. But assuming it is true, we get:
$$\frac{(2 + r)^{2^n} + (2 - r)^{2^n}}{2} \equiv 0\pmod p$$
$$(2 + r)^{2^n} + (2 - r)^{2^n} \equiv 0\pmod p$$
$$(2 + r)^{2^n} \equiv - (2 - r)^{2^n} \pmod p$$
Multiplying both sides by $(2 + r)^{2^n}$ and then squaring:
$$(2 + r)^{2^{n + 1}} \equiv -1\pmod p$$
$$(2 + r)^{2^{n + 2}} \equiv 1\pmod p$$
We see an exponent for which we get residue 1 modulus p, and if it is the minimum one (the order), it must divide every other exponent which also gives 1 modulus p for the same base, in particular p - 1, which works for every base.
It is really the minimum one, because, if any other is the minimum, it needs to be in the form $2^k$, $k < n + 2$, because it must then divide $2^{n+2}$.
This is not possible because we would have $(2 + r)^{2^{n + 1}} \equiv 1\pmod p$ by squaring both sides of $(2 + r)^{2^k} \equiv 1\pmod p$ multiple times, and we know the truth is $(2 + r)^{2^{n + 1}} \equiv -1\pmod p$.
We now get:
$$2^{n + 2} | p - 1$$
Since p + 1 is also even, the product $p^2 - 1 = (p-1)(p+1)$ must be divisible by $2^{n+3}$.
