 mersenneforum.org > Math Representing x^2+3y^2
 Register FAQ Search Today's Posts Mark Forums Read 2005-08-01, 23:38 #1 Zeta-Flux   May 2003 154710 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   2005-08-03, 01:16 #2 maxal   Feb 2005 25210 Posts 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   2005-08-03, 01:34 #3 Zeta-Flux   May 2003 60B16 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   2005-08-03, 05:27 #4 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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^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).   2005-08-03, 18:40   #5
maxal

Feb 2005

22·32·7 Posts 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.   2005-08-03, 21:10 #6 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 21378 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^(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 (BSqrtQ) 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

 Thread Tools Show Printable Version Email this Page

All times are UTC. The time now is 04:10.

Mon May 17 04:10:56 UTC 2021 up 38 days, 22:51, 0 users, load averages: 4.04, 3.51, 2.95