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.

  • $\begingroup$ This looks like the Lucas-Lehmer test $\endgroup$ – J. W. Tanner Aug 28 '19 at 19:16
  • $\begingroup$ Ah, yes, with $s_n=2w_n.$ Then $s_{n+1}=4w_n^2-2=s_n^2-2.$ $\endgroup$ – Thomas Andrews Aug 28 '19 at 19:20
  • $\begingroup$ 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. $\endgroup$ – user645636 Aug 28 '19 at 20:00
  • $\begingroup$ tempted to write long answer and show many other forms.math.stackexchange.com/questions/3143684/… $\endgroup$ – user645636 Aug 29 '19 at 11:47

I believe you have re-discovered the Lucas-Lehmer test. For a proof, see this Wikipedia article.


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.

As to the proof, it follows from the fact that 2 is not a divisor of any Mersenne number, so it won't affect if it divides the sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.