20050801, 23:38  #1 
May 2003
7×13×17 Posts 
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 
20050803, 01:16  #2 
Feb 2005
252_{10} Posts 
The formula is similar to the one for r_{2}(n) given at http://mathworld.wolfram.com/SumofSquaresFunction.html.
Let n be represented as n = 3^{c} p_{1}^{2a[sub]1[/sub]} ... p_{n}^{2a[sub]n[/sub]} q_{1}^{b[sub]1[/sub]} ... q_{r}^{b[sub]r[/sub]}, where p_{1}, ..., p_{n} are primes of the form 3k+2, and q_{1}, ..., q_{k} are primes of the form 3k+1. Let B=(b_{1}+1)...(b_{r}+1). Then the number of representations n=x^2+3*y^2 equals 0 if either of a_{i} is a halfinteger; 6B if n is a multiple of 4; 2B otherwise. Last fiddled with by maxal on 20050803 at 01:22 
20050803, 01:34  #3 
May 2003
7·13·17 Posts 
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 
20050803, 05:27  #4 
"Phil"
Sep 2002
Tracktown, U.S.A.
1118_{10} Posts 
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^30213771 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). 
20050803, 18:40  #5  
Feb 2005
FC_{16} Posts 
Quote:
I would solve this problem via computing (3)^(1/2) mod Mp which is quite unrelated to the Euclidean algorithm. 

20050803, 21:10  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
2·13·43 Posts 
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^(EXP2)) mod Q ; This was done using George Woltman's code in pfgw IF (B>Q/2) THEN B=QB 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((QB^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. 