Re: How to find a solution to this equation so the result is a perfect square ?

[Kurt Foster <drsardonicus@earthlink.net>]

On Feb 13, 2025, at 8:05 AM, Laël Cellier wrote:

> So, do you mean only square roots of a are the solution ? In the  
> current example, I volontarily took a long a in the case it’s hard  
> to factorize (up to 1024). On the other end, I don’t need a  
> specific end result, but just for it to be a square…
>
> And even then, what about the case I know a square root of  
> 20422354090808007360481140437163150058277495681745577657420405131241  
> mod  
> 53919893334301279589334030174040979997534463873026188556492192357233  
> (taking back the example) ?

Taking Denis Simon's formulation

y^2 - N*z^2 == 0 (mod a)

with

N =  
20422354090808007360481140437163150058277495681745577657420405131241 and

a = 53919893334301279589334030174040979997534463873026188556492192357233

I first check that N and a are relatively prime:

> ?  
> gcd 
> (20422354090808007360481140437163150058277495681745577657420405131241,53919893334301279589334030174040979997534463873026188556492192357233 
> )
> %1 = 1

Assuming further that gcd(z, a) ==1 we have

(y/z)^2 == N (mod a).

I note that assuming that y and a are also relatively prime, there is  
no solution unless N is a quadratic residue modulo every prime factor  
of a.  OK, factoring "a" we have

> ?  
> factor 
> (53919893334301279589334030174040979997534463873026188556492192357233)
>
> %2 =
> [5192296858534827628530496329220121 1]
>
> [10384593717069655257060992658440473 1]

Pretending we don't know from the example that N is in fact a  
quadratic residue modulo each prime factor, and checking,

> ? p1=%2[1,1];p2= 
> %2 
> [2,1 
> ];N 
> =20422354090808007360481140437163150058277495681745577657420405131241;
> ? kronecker(N,p1)
> %4 = 1
> ? kronecker(N,p2)
> %5 = 1

OK, now we extract square roots of N modulo each prime factor, and use  
CRT to get all possible values of y/z (mod a):

> ? sqrt(Mod(N,p1))
> %6 = Mod(224635834423632839306016528458225,  
> 5192296858534827628530496329220121)
> ? sqrt(Mod(N,p2))
> %7 = Mod(4522202310821969556787916053134856,  
> 10384593717069655257060992658440473)

> ? chinese(%6,%7)
> %8 =  
> Mod 
> (49758565764982590856078871380073331629592230703205690186378482038585 
> ,  
> 53919893334301279589334030174040979997534463873026188556492192357233)
> ? chinese(%6,-%7)
> %9 =  
> Mod 
> (30324503141575450758959658433422525480164049178623057876318164013414 
> ,  
> 53919893334301279589334030174040979997534463873026188556492192357233)
> ? chinese(-%6,%7)
> %10 =  
> Mod 
> (23595390192725828830374371740618454517370414694403130680174028343819 
> ,  
> 53919893334301279589334030174040979997534463873026188556492192357233)
> ? chinese(-%6,-%7)
> %11 =  
> Mod 
> (4161327569318688733255158793967648367942233169820498370113710318648 
> ,  
> 53919893334301279589334030174040979997534463873026188556492192357233)
> ?

The reader can check that for the given solution, y/z is the last of  
these square roots, i.e.

  21/519229685853482762853049632922093 ==  
4161327569318688733255158793967648367942233169820498370113710318648  
(mod a)

I leave the complications of when the modulus a is not square free, or  
when gcd(z, a) > 1, etc to others.