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

[Tony Reix]

There is a theorem (proven by Euler and used for proving the case n=3 of Fermat's Last Theorem), saying that:
if p is of the form: p = 1 + 3n and is prime, then there is a unic pair (A,B) such that: p = A^2 + 3B^2 (I).

Since Mersenne prime numbers are of the form: Mq = 1 + 6qk , this theorem applies.

The table here after shows the results for q = 1 to 31 .

Is seems that:
[code:1]
1) if q = 3, then (I) is true.
2) if q >=5 and Mq are both prime numbers, then:
A=2a and B=3b, showing: Mq = (2a)^2 + 3(3b)^2 (II).
3) if q is prime and Mq is not prime, then there is no solution (A,B) to (I).
4) if q = 2 or q is not prime, then, either (I) has no solution or (I) has several solutions (possibly with (II)).
[/code:1]

About (II), it's easy (based on my theorem: Mq = (8x)^2 - (3qy)^2 ) to prove that A=2a (proof a contrario: B can't be equal to 2b).
But I failed founding a proof for: B=3b .
Either this is true only for some q such that Mq is prime (including q=5,7,13,17,19,31), or it is true for all prime q such that Mq is prime.

[code:1]
q Mq (2a)^2 + 3(3b)^2 A^2 + 3B^2
-----------------------------------------------
a b A B
-----------------------------------------------
1 1 1 0
2 3 0 1
P 3 7 2 1
4 15
P 5 31 1 1
6 63 3 1
P 7 127 5 1
8 255
9 511 11 1
2 13
10 1023
p 11 2047
12 4095
P 13 8191 23 15
14 16383 54 67
126 13
15 32767 29 33
79 17
110 83
178 19
16 65535
P 17 131071 181 1
18 262143 45 97
153 79
225 47
243 31
P 19 524287 149 127
20 1048575
21 2097151 169 271
479 209
74 835
938 637
1226 445
1442 77
22 4194303
p 23 8388607
24 16777215
25 33554431 383 1105
2209 721
2651 449
2749 351
26 67108863
27 134217727 5249 943
28 268435455
p 29 536870911
30 1073741823
P 31 2147483647 23081 783
[/code:1]

Does someone can find a proof for B=3b ?

[Tony Reix]

Since I think my previous note may be unclear, here are some clarifications.

When q and Mq are primes
1) it is certain that Mq = A^2 + 3*B^2, and (A,B) is unic.
2) it's easy to prove that A is always pair, so A = 2*a .
3) It seems that B is always 0 (mode 3).
Examples
M19 = (2* 149)^2 + 3*(3*127)^2
M31 = (2*23081)^2 + 3*(3*783)^2

I dont' know if this formula [Mq = (2*a)^2 + 3*(3*b)^2 ] may be useful, but I'd like some help for proving (or not!) that B=3*b .

Is someone interested searching this proof ?

The proof of the basic theorem (p = a^2 + 3b^2) can be found at
http//www.mathpages.com/home/kmath009.htm
LEMMAs 1 to 5 .

[philmoore]

I haven't made any headway on your conjecture yet, that B always = 3*b for some b, but I did check that it holds for the next four Mersennes, q=61, 89, 107, and 127.

I also found solutions to 2^37-1=A^2+3*B^2. They are:
370682^2+3*3357^2 and 284714^2+3*137085^2.
(Note that B is divisible by 3 in both cases.) In general, any integer will have representations of the form A^2+3*B^2 if all its factors are either 3 or =1 mod 3. Since 2^11-1=23*89, and both factors are =2 mod 3, there will be no such representations for it. It looks like 2^67-1, 2^101-1, and 2^103-1 are the next Mersenne numbers with prime exponents which will have such representations.

By the way, the book by Crandall and Pomerance has a good section, 2.3, which tells how to find representations of the form x^2+d*y^2 of a given prime p. I applied the algorithm given there to the factors of 2^37-1 and then used the identity:
(x^2+d*y^2)(z^2+d*w^2)=(xz+/-dyw)^2+d(xw-/+yz)^2.
Your case, d=3, is particularly interesting to us because it applies to all Mersenne primes.

[Tony Reix]

Hello, thanks for looking at this conjecture !

I did check that it holds for the next four Mersennes, q=61, 89, 107, and 127.

Good ! :D
Would you mind providing the value of (a,b) you found for these 4 Mersenne primes ?

About M27, which is not prime, I missed the pair (a,b) = (14801,43375) , [with formula (II) : A=2a and B=3b]. ops:

In general, any integer will have representations of the form A^2+3*B^2 if all its factors are either 3 or = 1 mod 3.

This is not exactly what LEMMA 4 says in: http://www.mathpages.com/home/kmath009.htm
[code:1]
LEMMA 4: If the integer N is representable in the form A^2 + 3B^2 with (A,3B)=1, then the only odd prime factors of N are of the form p = 3k+1.
[/code:1]
A and 3B must be co-prime in order that each prime factor is of the form 1 (mod 3).
Is there something I missed ?

I don't have the the book by Crandall and Pomerance. Can you summarize the algorithm given in section 2.3 ?

Do you mean the conclusion is:
If we prove: {non-prime Mersenne numbers whith q prime can't be represented as A^2+3B^2}, then: {their prime factors are only of the form: 2+3k}.
And thus, during first step of Prime95: {try with small prime factors of form: 1+2qk}, one may: {remove those factors that are of the form: 1+3k } ?
That would speed up the search.
Is that true (or maybe already well known) ?

[Tony Reix]

M29 = 2^29-1 = 233*1103*2089
233 = 2 (mod 3)
1103 = 2 (mod 3)
2089 = 1 (mod 3)
And I found no (A^2+3*B^2) representation for M29.

M67 = 2^67-1 = 193707721 * 761838257287
193707721 = 1 (mod 3)
761838257287 = 1 (mod 3)

Factors of M37, M101 and M103 also are 1 (mod 3).

Do you have the representation of M67, M101 and M103 ?

Does it mean that M11 and M23 are special cases also for A^2+3*B^2 form ? as they are special for Mersenne
q=4k-1 and 2q+1 is prime ==> Mq is not prime (If I remember correctly).

And, for q=67,101,103 (which are 4k-1), 2q+1 is not prime.

What about q= 37, 41, 43, 47, 53, 59, 61 ?
Factors of M37 are 1 (mod 3).

About q=53, 2q+1=107 is prime.
And M53=6361*69431*20394401 where 6361 is 1 (mod 3) and others are 2 (mod 3).

[philmoore]

Yes, here are the solutions for M61 through M127:

M61=1505304098^2+3*115329357^2
M89=17376907720394^2+3*10279641655875^2
M107=9286834445316902^2+3*5033685952807971^2
M127=9328321181472828398^2+3*5263826472436016979^2
(Of course, a=A/2, b=B/3.)

About lemma 4, it doesn't exactly say the same thing, it is sort of a converse to my statement, but I don't think there is a contradiction: If you drop the condition that A and 3B do not have a common factor, it is possible to also include the factor 3 as well as primes = 1 mod 3. I didn't state the necessary conditions, I just said that if all factors are 1 mod 3 or 3, then representations exist, but it is possible to get representations in other cases: 175=10^2+3*5^2, but of course here, A and B have a common factor. Lemma 4 correctly states the necessary conditions in the case (A,3B)=1, i.e., that each p=3k+1.

I found some really good stuff on this topic last night. (For those who are interested, my references were "Primes of the Form x^2+ny^2" by David A. Cox and "A Classical Introduction to Modern Number Theory" by Kenneth Ireland and Michael Rosen.) A conjecture of Euler (neither book tells who proved it) is that a prime p can be represented as x^2+27*y^2 if and only if two conditions are met: p must be = 1 mod 3, and 2 must also be a cubic residue mod p. (I.e., the equation x^3=2 mod p must have solutions.) It turns out that both conditions are true for Mersenne primes with p>3, therefore, B must always be divisible by 3. But the proof used cubic reciprocity and was not easy! (I wonder if there is an easier proof that applies in this case.) You can see why 2 must be a cubic residue mod q, since 2^q=1 mod Mq: For q=17, for example, let x=2^6. Then x^3=(2^6)^3=2^18=2 mod M17=2^17-1. Or for q=19, let x=2^13, and x^3=2^39=2*(2^19)^2=1 mod M19. The only cases where this will not work is if the exponent is divisible by 3, but the only Mersenne prime with such an exponent is M3=7.

I don't have the Crandall and Pomerance book with me, but I'll bring it tomorrow and describe the algorithm. There were easy and difficult cases, but the Mersenne primes were fortunately covered by one of the easy cases.

[philmoore]

Yes, all factors of M29 would have to be = 1 mod 3 in order for a representation to exist. And if there are n distinct factors of Mq, and they are all = 1 mod 3, the number of positive integer solutions to Mq=x^2+3*y^2 will be 2^(n-1).

I don't have the solutions for M67, M101, M103, etc. Doing M37 got in to the difficult case of the algorithm, but maybe I might have a chance to get it working this weekend.

[flava]

I did a quick check at work today and M37 has two solutions, the first one with b between 3000 and 4000 and b=9*k. I did not write it down but I'll look for it tommorow. All other primes < 61 don't have solutions (I mean those p where 2^p-1 composite). Unless I screwed up something writing the program.

Huh, I should have read philmoore's early post ops:

[philmoore]

Here is an algorithm which, given a Mersenne prime p=2^q-1 for q>2, will find the unique solution in positive integers x and y to p=x^2+3*y^2.

b=3^(2^(q-2)) mod p;
if 2b>p, b=p-b;
a=p;
s=floor(sqrt(p));
do while b>s
{t=a mod b; a=b; b=t}
x=b;
y=sqrt((p-x^2)/3);
end;

The first step computes b as a square-root of -3 mod p. It can be done in q-2 squarings mod p, and would take about the same time as a Lucas-Lehmer test of p. The second step adjusts b so that it is the smaller of the two square-roots in the interval (0,p-1). Steps 3 and 4 are initialization for the main loop which follows. This loop essentially follows the Euclidean algorithm until b is less than the square-root of p. Now x is b and y is computed in the last step.

If p=2^q-1 is composite, the problem is not so easy! We first must find the factors of p, and hope that they are all = 1 mod 3. Then for each factor f, we have to do a computation similar to that above. The tricky part is finding a square-root of -3 mod f. Crandall and Pomerance give an easy algorithm for this if f = 3, 5, or 7 mod 8, but the case f=1 mod 8 requires a little more work. (Note that Mersenne primes are all = 7 mod 8, one of the easy cases.) If you are interested in this algorithm, let me know and I'll post it tomorrow.

Phil

[flava]

M67 = 10106743618^2 + 3*3891344499^2

[Tony Reix]

Thanks for all the information. :D

I've noticed that, for q and Mq both primes, in the formula (II) : Mq = (2*a)^2 + 3*(3*b)^2 , a is always greater than or equal to b. That's true for: q=5,7,13,17,19,31,61,89,107,127.
(But we don't have A=2a>=B=3b for all of them : q=19, A=298,B=381).
This also may be a property shared by all Mersenne primes numbers. :idea:

Hi philmoore, flava, which tool do you use for running the algorithm ?

Since M67 is not prime, it should have 2 representations ?!