# Mersenne primes and the sequence $w_0=2,w_{n+1}=2w_n^2-1$

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:

1. $$w_n = \frac{1}{2}\left((2+\sqrt 3)^{2^n}+(2-\sqrt 3)^{2^n}\right)$$
2. $$w_n = T_{2^n}(2),$$ where $$T_k$$ are the Chebyshev polynomials of the first kind.
3. 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.

• This looks like the Lucas-Lehmer test – J. W. Tanner Aug 28 '19 at 19:16
• Ah, yes, with $s_n=2w_n.$ Then $s_{n+1}=4w_n^2-2=s_n^2-2.$ – Thomas Andrews Aug 28 '19 at 19:20
• Also compare this to $2x^2+4x+1$ which doubles and adds 1 to the exponent if $x$ is a Mersenne. Hence iterating it starting with $x=1$ we get the Double Mersennes. – user645636 Aug 28 '19 at 20:00
• tempted to write long answer and show many other forms.math.stackexchange.com/questions/3143684/… – user645636 Aug 29 '19 at 11:47

This is what I call the reduced Lucas-Lehmer test. The original can also use start values in A018844 . Noting that all terms after the first in this reduced form of the LL test are odd, we can also reduce it to the $$k$$ values such that the sequence is $$2k+1$$ (as well as $$3l+1$$), and check if they are $$M_{n-1}\bmod M_n$$. This also goes to $$32j+1$$ etc (building the coefficient in powers of 2) as the terms increase in size. The $$k$$ values are linked by $$k\to 4k^2+4k$$ . We also have that any divisor of this reduced sequence, goes from 0 to -1 to 1 under mod which means we can use it to prove infinitely many normal primes. If we could force a proof of a new Mersenne as a prime factor, we'd prove infinitely many Mersenne primes (a currently unsolved problem). So there are quite a few possibly interesting implications from this sequence.