20220507, 23:34  #12  
"Rashid Naimi"
Oct 2015
Remote to Here/There
8DA_{16} Posts 
You can always try to find the squares by trial and erfor. After all that is the Fermat’s factorization method. But:
Quote:
For a formulaic solution to the problem, well it’s been a work in progress for centuries now. No proof that it can’t exist AFAIK. 

20220508, 02:26  #13  
Feb 2017
Nowhere
13400_{8} Posts 
Quote:
I find this easiest to do using the complex factors a + b*I and a  b*I of a^2 + b^2. But it's a little tricky, because you have to choose the "correct" conjugate divisor of each prime factor. You only get one representation of the cofactor, of course. The following is ridiculously clunky, but it gets the job done. Code:
? { v=[114689, 26017793, 63766529, 190274191361, 1256132134125569, 568630647535356955169033410940867804839360742060818433]; s2sq=Qfb(1,0,1); w=vector(#v, i, qfbsolve(s2sq,v[i])*[1,I]~); z=I+2^2048; for(i=1,#w,if(gcd(w[i],z)==1,w[i]=conj(w[i]))); q=z/prod(i=1,#w,w[i]); print(abs(real(q))); print(); print(abs(imag(q))) } 200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916 11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591 

20220519, 23:50  #14 
Mar 2016
2^{2}×101 Posts 
A peaceful and pleasant night for you,
if a compositon of n=x²+y² exists and n not a prime, how many different compostions exist depending of the number of factors of n ? Please have patience with me, I try to do progress in math and invite other to participate. 
20220520, 00:54  #15  
Feb 2017
Nowhere
2^{8}·23 Posts 
Quote:


20220604, 18:25  #16 
Mar 2016
2^{2}×101 Posts 
A peaceful day for you,
Is there a known algorithm for x²+y²=m²+n²=d mod f I think it is easier than to find x²+y²=0 mod p Any interesting suggestion how to speed up Gimps ? I really need a new Mp. Last fiddled with by bhelmes on 20220604 at 18:36 
20220606, 12:38  #17 
Feb 2017
Nowhere
2^{8}·23 Posts 
Let g = gcd(d, f).
Last fiddled with by Dr Sardonicus on 20220608 at 15:27 Reason: Strike out incorrect criterion 
20220608, 11:44  #18 
Mar 2016
2^{2}×101 Posts 
A peaceful and pleasant day for you,
I miss the case 4. g=1 and f odd I am searching for x²+y²=m²+n²=d mod f, resp. two sums of squares with the same norm d mod f. Algorithm: choose a value r>0 and a start point x²+y²>f+r with x>y if x²+y²>f+r then x:=x1 if x²+y²<f then y:=y+1 if x²+y² > 0 mod f and x²+y² < r mod f store the pair with the norm and y:=y+1 if two points with the same norm is found stop the algorithm. A visualisation and examples for small numbers can be found under http://devalco.de/unit_circle/system_tangens.php Is there a better algorithm available ? 
20220608, 16:10  #19 
Feb 2017
Nowhere
2^{8}·23 Posts 
I was completely wrong about the criterion for g > 1 with g = gcd(d, f). I struck it out.
As an example, x^2 + y^2 == 3 (mod 15) is solvable (e.g. x = y = 3). I had failed to consider that x^2 + y^2 could be divisible by a higher power of a prime than g, but the congruence (mod f) could still hold. Mea culpa A better approach is probably to factor the modulus f, and solve x^2 + y^2 == d (mod p) for each prime factor p of f. If f is divisible by a higher power of p, such solutions can be "lifted" to solutions mod p^2, etc. If p is prime, one way to solve x^2 + y^2 == d (mod p) [assuming r is not 0 (mod p)] is by trial. Trying y = i = 0, 1, 2, etc. factor x^2 + i^2  d (mod p). If it splits into linear factors, they give solutions to x^2 + i^2 == d (mod p). This should turn up a couple of solutions in fairly short order. If d is 0 (mod p) there is always the solution x = y = 0 (mod p). If p = 2 there is the solution x = y = 1 (mod 2). If p is congruent to 1 (mod 4) there are several solutions. Again, if f is divisible by a higher power of p, solutions mod p can be "lifted" to solutions mod p^2, p^3, etc. Finally, solutions modulo the prime (power) factors of f can be combined using the Chinese Remainder Theorem. Take d = 3, f = 15. x^2 + y^2 == 3 (mod 3) [i.e. 0 mod 3] has the solution x = y = 0 (mod 3). x^2 + y^2 = 3 (mod 5): Trying i = 0, no luck; i = 1, no luck. Trying i = 2, x^2 + 1 = 0 (mod 5) has the solutions x = 2 or 3 (mod 5). Combining the mod 3 and mod 5 solutions we get 12^2 + 12^2, 3^2 + 12^2, and 3^2 + 3^2 == 3 (mod 15). Last fiddled with by Dr Sardonicus on 20220608 at 16:11 