**Puzzle 298. Mersenne,
Mq
= (8x)^2 - (3qy)^2**

**Tony Reix** poses the following puzzle:

**Mersenne numbers (Mq=2^q-1) are of the form:
Mq = (8x)^2 - (3qy)^2.**

**Questions:**

**1. Prove it.**

2. Do you devise any interesting application of the above result?

Contributions came from: **Richard Pinch, Rudolph
Knjzek, Dan Dima, John Arion & Ken Wilke**. Most of them saw immediately
that the **Reix**'s statement holds for q prime greater than 3.The
proofs sent for the same statement is very similar to the following one:

**Richard Pinch** wrote:

We assume that in this puzzle q is intended to be prime
and >= 5.

The statement is not true when q is even, for example, as then (8x)^2 and
(3qy)^2 would both be divisible by 4. It is also false when q=9, for
example, as 511 can only be expressed as 40^2-33^2 or 256^2-255^2 and
neither of these fits. We check that when q=3 we have 7 = 4^2-3^2 only and
this doesn't fit either.

In passing we note that the expressions of any odd number n as a
difference of two squares correspond to its factorisations: n = a.b = ((a+b)/2)^2
- ((a-b)/2)^2; n = u^2 - v^2 = (u+v)(u-v). This is how we can be sure that
there are no more expressions for 511 and 7 above.

Now suppose that q>=5 and q is prime. We have 2^q-1 = (2^(q-1))^2 -

(2^(q-1)-1)^2 = u^2 - v^2 say. Since q>=5, we have 16 dividing u.

Further, q is odd so 2^(q-1) is congruent to 1 mod 3, so 3 divides v, and
q is prime so 2^(q-1) is congruent to 1 mod q, so q divides v. But q is
prime and q>3, so 3 and q are coprime and 3q divides v.

As a final note, the statement is true when q is a pseudoprime not
divisible by 3, such as 341 = 11.31, as then it is again true that

2^(q-1) is congruent to 1 mod q.

***

Regarding the question 2:

**Dan Dima** wrote:

Clearly, a useful application is to establish if M_q is
a prime Mersenne. (for the 2nd part) It is easy to see that the equation:
2^q-1=(8x)^2-(3qy)^2 may have a finite number of solution in integers (x,y)
as a Pell equation, since we can find easily upper bounds for x,y:

x <= (2^q - 1)/8 ;

y <= (2^(q-1) - 1)/(3q)

If it has more than one integer solution, then M_q for q-even is clearly
composite, otherwise we can't predict if this a Mersenne prime using only
this!

If we search for duplicated solutions up to this bounds, the computational
time decreases but not significant. On the other hand if the 1st and 2nd
integer solutions arise earlier, the problem is done and it really helps.

**John Arioni** wrote:

...an application of the above result could be that the
primality of an odd integer q can be first tested by dividing (2^(q-1)-1)
/ 3 ( binary sequence 10 10 10 … 101 ) by q instead of dividing 2^(q-1)-1
(sequence 11 11 11 … 11 ).

***