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

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 ).

***