mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-08-01, 23:38   #1
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default Representing x^2+3y^2

Let n be a positive integer. There is a very nice formula for the number of ways n can be represented by the quadratic form x^2 + y^2, in terms of the prime factors of n. Does anyone know of a similar formula for the form x^2+3y^2?

Thanks
Zeta-Flux is offline   Reply With Quote
Old 2005-08-03, 01:16   #2
maxal
 
maxal's Avatar
 
Feb 2005

25210 Posts
Default

The formula is similar to the one for r2(n) given at http://mathworld.wolfram.com/SumofSquaresFunction.html.

Let n be represented as
n = 3c p12a[sub]1[/sub] ... pn2a[sub]n[/sub] q1b[sub]1[/sub] ... qrb[sub]r[/sub],
where p1, ..., pn are primes of the form 3k+2, and q1, ..., qk are primes of the form 3k+1.

Let B=(b1+1)...(br+1). Then the number of representations n=x^2+3*y^2 equals

0 if either of ai is a half-integer;
6B if n is a multiple of 4;
2B otherwise.

Last fiddled with by maxal on 2005-08-03 at 01:22
maxal is offline   Reply With Quote
Old 2005-08-03, 01:34   #3
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

Seems correct. That is what I guessed, but I couldn't find any official source for it. It turns out I don't need an official proof after all, so I'll just believe you got it right!

Thanks,
Pace
Zeta-Flux is offline   Reply With Quote
Old 2005-08-03, 05:27   #4
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111810 Posts
Default

Of course, 2 is a prime = 2 mod 3, so if n is divisible by 4, it must contain an even power of 2 in order to have representations. So Maxal's observation implies than an n divisible by 8 but not by 16 has zero representations.

By the way, I was solving the equation x^2+3y^2=Mp for all Mersenne primes Mp last spring using script files with pfgw, but stopped at Mp=2^3021377-1 because the Euclidean algorithm as implemented in my script file was a bottleneck. Still, it was fun solving Diophantine equations with such huge solutions (450,000+ digits).
philmoore is offline   Reply With Quote
Old 2005-08-03, 18:40   #5
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

Quote:
Originally Posted by philmoore
By the way, I was solving the equation x^2+3y^2=Mp for all Mersenne primes Mp last spring using script files with pfgw, but stopped at Mp=2^3021377-1 because the Euclidean algorithm as implemented in my script file was a bottleneck.
What method do you use to find x,y?
I would solve this problem via computing (-3)^(1/2) mod Mp which is quite unrelated to the Euclidean algorithm.
maxal is offline   Reply With Quote
Old 2005-08-03, 21:10   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

2·13·43 Posts
Default

I checked again, and see that I actually went as far as x^2 + 3*y^2 = M6972593 before the GCD implementation was starting to take longer than the powering algorithm.

I believe this is called "Cornacchia's algorithm" or some variant of it:

Q = 2^EXP - 1 ; (This is the Mersenne prime)
SqrtQ = SQRT(Q)
B = 3^(2^(EXP-2)) mod Q ; This was done using George Woltman's code in pfgw
IF (B>Q/2) THEN B=Q-B
A = Q
IF (B<SqrtQ) GOTO Loop_end
Loop_start
T = A mod B
A = B
B = T
IF (B>SqrtQ) GOTO Loop_start
Loop_end
A = SQRT((Q-B^2)/3)

As you see, I wasn't actually using the GCD algorithm to the end, I only went until B<SqrtQ, so before going on to M13466917, I need to write a more efficient implementation than is available in the SCRIPT file capability of the development version of pfgw.
philmoore is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:31.

Sun Dec 6 01:31:00 UTC 2020 up 2 days, 21:42, 0 users, load averages: 2.36, 2.57, 2.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.