Given the sequence $w_0=2, w_{n+1}=2w_n^2-1.$
It appears, from purely numeric examples, that we have this result:
When $q$ is an odd prime number, then $M_q=2^q-1$ is prime if and only if $M_q\mid w_{q-2}.$
I can actually prove if $M_q\mid w_{q-2}$ then $M_q$ is prime. [See below.] So the tricky part is if $M_q$ is prime, is $M_q\mid w_{q-2}?$
Can anybody find a proof or disproof of this?
I've tested this for the Mersenne primes $M_q$ with $q<10000.$
Some properties of $w_n$ are:
- $w_n = \frac{1}{2}\left((2+\sqrt 3)^{2^n}+(2-\sqrt 3)^{2^n}\right)$
- $w_n = T_{2^n}(2),$ where $T_k$ are the Chebyshev polynomials of the first kind.
- The values of $w_n$ are pair-wise relatively prime.
This came about initially from this question. In my answer there, I show that if we have an odd prime factor $p\mid w_{n}$ then:
A. If $p\equiv 1\pmod{12}$ then $2^{n+2}\mid p-1.$
B. It is not possible that $p\equiv -1\pmod{12}.$
C. Otherwise $2^{n+2}\mid p^2-1.$
We can show that if $M_q\mid w_{q-2}$ then $M_q$ is prime using $(A)$ and $(C)$.
If $p\mid M_q$ and $M_q\mid w_{q-2}$ then by (C) and (A), you have that $2^q\mid p^2-1.$ This means that $2^{q-1}\mid p+1$ or $2^{q-1}\mid p-1.$ In either case, $p\geq 2^{q-1}-1=\frac{M_q-1}{2}.$ But this isn't possible unless $p=M_q$ since otherwise, $3p>M_q$ and $M_q$ is odd.
Best Answer
I believe you have re-discovered the Lucas-Lehmer test. For a proof, see this Wikipedia article.