Re: question on trying to use quadratic residues to eliminate needless checks

[Denis Simon <denis.simon@unicaen.fr>]

Dear Randall,

I am not sure I understand your question.
You want to solve a^2+b^2=s^2, where a is given, and b,s are integers or half integers ?

In this case, you write your equation as
b^2 = s^2-a^2 = (s-a)(s+a)
and you loop over the divisors of b^2, say b^2 = p*q
then s = (p+q)/2 and a = (p-q)/2

Denis.

----- Mail original -----
> De: "American Citizen" <website.reader3@gmail.com>
> À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Lundi 24 Mars 2025 01:55:50
> Objet: question on trying to use quadratic residues to eliminate needless checks

> Hello:
> 
> I am trying to determine if using quadratic residues will shorten down
> the time to check two numbers, a,b such that a^2 + b^2 = square (say s^2)
> 
> In regard to body cuboids, I looked at the side = 288807105787200
> 
> Using the divisors of side^2, we find that 1,492,627 integers or
> fractions exist, such that x^2 + 288807105787200^2 = s^2 where x is in Z
> or Q (actually n/2)
> 
> There are 1,262,992 integers with this property and 229,635 rationals
> (all have denominator 2) with this property.
> 
> I am looking for two numbers r,s from this pile of 1,492,627 values such
> that r^2 + s^2 = t^2 (t either integer or rational)
> 
> Two examples:
> 
> 288807105787200^2 + 1944335775346650^2 = 1965668118387750^2
> 
> 288807105787200^2 + (2560559305082625/2)^2 = (2624900404254975/2)^2
> 
> Naively running through this batch of 1,492,627 values requires
> 1,113,966,934,251 checks to see if r^2 + s^2 is a square.
> 
> This is taxing, even for my 6 core Intel Xeon 3.5 Mhz system and
> requires several days to run.
> 
> Is there a way, using quadratic residues, to eliminate most of the pair
> checks and reduce the running time?
> 
> Randall
> 
> P.S. I have been running for about a day now and only about 1/4 the way
> done.