Mq prime, then: Mq = A^2 + 3B^2 with A=2a. (and B=3b ??)

[jocelynl]

Mq = (2*a)^2 + 3*(3*b)^2

Should we look at k`s of (N-1) to see if there`s a corralation with this
as 2 and 3 always divides (N-1)?

[flava]

Tony, I use Msdev 6.0 and a the GMP lib to write my big number toys :(
BTW, I tested philmoore's algorithm for 2^p - 1 with p prime < 5000 and the only good solutions are given by Mersenne primes.
A test up to 100.000 would take a day or two, the algorithm is a bit slower than LL.

About M67 you are right, it has a second solution:
M67 = 9845359982^2 + 3*4108642899^2

[jocelynl]

flava don`t forget M37
M37 = (284714)^2+3*(137085)^2

[philmoore]

Tony, I did my calculations with MAPLE, but I think it is limited to numbers with a few thousand digits, so GMP would be the logical choice to extend these computations.

The algorithm I described works only on primes. The second part, the modified Euclidean algorithm, is called the Cornacchia-Smith algorithm in Crandall and Pomerance, and works to find solutions, when they exist, to p=x^2+k*x^2. (-k must be a square-root mod p, p must be a prime.) Finding a square-root of a mod p is the first part of the algorithm, and is described in more detail in Crandall and Pomerance. Here is a summary of their algorithm to find a solution x to the equation x^2=a mod p:

(Check first that a is a square mod p by evaluating the Jacobi symbol.)
Case 1: p=3 or 7 mod 8. (This case covers Mersenne primes.)
return x=a^((p+1)/4) mod p;
Case 2: p=5 mod 8.
x=a^((p+3)/8) mod p;
if (x^2=a mod p) return x; (Otherwise, x^2=-a mod p.)
return x=x*2^((p-1)/4) mod p;
Case 3: p=1 mod 8. (This is the hardest case.)
First find a random d with 1<d<p such that d is not a square mod p. This is done by evaluating Jacobi symbols.
Write p-1=(2^s)*t with t odd.
A=a^t mod p; (The next three lines are loop initialization.)
D=d^t mod p;
m=0;
for i=0 to s-1 {if((A*D^m)^(2^(2-1-i))=-1 mod p) m=m+2^i}
return x=a^((t+1)/2)*D^(m/2) mod p;

If you wanted to solve 2^67-1 = x^2 + 3*y^2, you would first have to find the factors 2^67-1=193707721*761838257287. The second factor = 7 mod 8, so it is easy to find a square-root of -3 = 761838257284 mod 761838257287. Then let b=x and run the Cornacchia-Smith algorithm to get:
761838257287=16462^2 + 3*503841^2.
The second factor 193707721 is = 1 mod 8 and falls under case 3. Checking 2, 3, 5, 7, etc., the first prime value of d which is not a square mod 193707721 turns out to be 17. a=193707721-3, so we run the algorithm to find that x=42821145. Then Cornacchia-Smith gives us:
193707721 = 7939^2 + 3*6600^2.
Finally, to solve the problem for 2^67-1, we let
x = 16462*7939 +/- 3*503841*6600 and
y = 16462*6600 -/+ 503841*7939
to get the solutions Flava posted above. If anyone is interested in solving the problem for 2^101-1 and 2^103-1, this should work.

I'm especially intrigued, though, by the cases where Mq=2^q-1 is a Mersenne prime. It would be interesting to see the solutions to x*2+3*y^2=Mq all plotted on the same graph. You could plot positive and negative values for x and y which would give the graph a pleasing symmetry. The integer solutions to x*2+3*y^2=Mq would consist of four points on an ellipse with major axis equal to sqrt(Mq). Scale each solution by the factor log(q)/(Mq) so that the axes of these ellipses would increase at an approximately equal rate. This would give you a very interesting representation of the 39 known Mersenne primes, wouldn't it? It might even give us some insight into Tony's observation that A=x/2 is so far always greater than B=y/2.

[Tony Reix]

Here is the (easy!) proof of A=2a for (q,Mq) both primes.

Mq = 2^q - 1 = A^2 + 3*B^2 .
Since Mq is odd, we have either (A odd, B even) or (A even, B odd).
Let say B=2b and A=2a+1.
Then 4*[2^(q-2)-3*b^2] = A^2 + 1 .
Thus 4 | (4a^2+4a+1) + 1 = 4k + 2 = 2*(2k+1).
That implies 2 | 2k+1 , which is impossible.
So A=2a and B is odd.

We have proven
Mersenne primes Mq = 4a^2 + 3B^2 , B odd.

I think there is a basic structure in Mersenne numbers, based on multiples of 4 and 3, since
1) (q,Mq) primes, Mq = 8x + 3qy = 2^(q-1) + M(q-1) and 2^(q-1) - M(q-1) = 1 .
2) My theorem says q prime, there is a pair (x,y) such that Mq = (8x)^2 - (3qy)^2 for each pair (a,b) such that Mq = a*b .
3) New theorem (q,Mq) primes, Mq = 4a^2 + 3b^2 .

[Tony Reix]

I made a mistake about M27.
There are 4 solutions
(a,b) = (5249,943)
(A,B) = (3350,6403) (7958,4861) (9470,3853)

[Tony Reix]

M37 has 2 (a,b) solutions
(185341,1119)
(142357,45695)
If we find the factors of a1-a2 and b2-b1, we find
(185341-142357) = 2^3 * 3^3 * 199
(45695-1119) = 2^5 * 7 * 199

199 !

Same thing for M67
(5053371809,1297114833)
(4922679991,1369547633)
(5053371809-4922679991) = 2 * 17 * 467 * 8231
(1297114833-1369547633) = 2^5 * 5^2 * 11 * 8231

8231 !

This can be a coincidence ?

[flava]

If you have any use for it, here is a link to a text file containing the solutions for Mersenne primes up to M86243. It has about 72K. http://membres.lycos.fr/gmk2000/mersenne/r86243.txt

[philmoore]

I realized last night that the algorithm I posted on 13 Feb admits a slight simplification. The first line was:

b=(p-3)^(2^(q-2)) mod p;

This can be replaced by:

b=3^(2^(q-2)) mod p;

since after the first squaring, it makes no difference whether we started with 3 or -3. I edited the above post to make the change.

I've also graphed the solutions computed by Tony and Flava and will upload a preliminary graph to this thread soon.

Phil M.

[Tony Reix]

Hi,
In an old French book about Arithmetic, I've found some theorems that apply to Mersenne numbers.
Some of them are close to things we already know about Mersenne numbers.

1) Prime numbers of the form p=8n-1 can be represented by an infinity of expressions x^2 - 2y^2.
Exple 7 = 3^2-2.1^2 = 5^2-2.3^2 ...
Not really useful.

2) Let's have a finite set E of prime numbers pi of the form 6n+1.
If we build P=p1*p2*p3...*pn , then all prime numbers q that divide 4P^2+3 are of the form q=6n+1 and q doesn't belong to E.
(This proves that the number of prime numbers of the form 6n+1 is infinite).
Do you notice 4P^2+3 ?!!
That is (still!) the coefficients 4 and 3 of Mq=(8x)^2-(3qy)^2 = 4a^2+3B^2 .
I tried to build a serie based on [Sn = 4*(Sn-1)^2 + 3 (mod Mq)] (like the LL test), but it did'nt build a nice symmetric tree finished by 0 like LL does. I can't see a clear schema in this tree with q=3 and q=5 .

3) Same thing with primes of the form p=8n-1 . Prime dividers of P^2-2 are of the form 8n-1 (and different to pi).
Here we find the famous LL test for Mersenne numbers Sn=Sn+1^2 - 2 !!

Let's take examples (with 1 number)
# p=31=P
- 4P^2+3 = 3847 = 6*641+1
- P^2-2 = 959 = 8*120-1 = 6*160-1
and 641=4*160+1
# p=127=P
- 4P^2+3 = 64519 = 6*10753+1
- P^2-1 = 16127 = 8*2016-1 = 6*(2^7*3*7)-1
and 10753 = 4*(2^7*3*7)+1
# also true for p=M13=8191

So it seems we have the relationships (where p=Mq)
4p^2+3 = 6*(4t+1)+1
p^2-2 = 6t-1
I don't know yet if it is evident or useful.

[Tony Reix]

In the previous discussions, we have considered A^2+3*B^2 = Mq (I) where A and B are integers.
If we now consider A and B as fractions, it appears that Mersenne primes seem to have many solutions to (I) while composed Mersenne numbers (with q prime) seem to have still no solution.
[code:1]
Examples:
4*( 17/ 7)^2 + 3*( 11/ 7)^2 = 31
4*(7*11/31)^2 + 27*(3*5/31)^2 = 31
4*( 61/31)^2 + 27*(9*7/31)^2 = 127 (with a < b !!)
( 1/ 2)^2 + 3*( 13/2)^2 = 127
( 89/ 2)^2 + 3*(7*13/2)^2 = 8191
[/code:1]
No solution found for M11, as expected.

(a/c)^2 + 3*(b/d)^2 = Mq <==> A^2 + 3*B^2 = Mq*C^2 where A,B,C are integers.