🚀 go-pugleaf

Ricky Laksanadjaja <lricky@earthcorp.com> writes:

>Hi,

>Does anybody know if there is a fast algorithm to solve the following
>problem?

>Equation:  x^2 - y^2 = z  , where  x is a positive integer, y is a
>positive integer, and  x > y, and z is a large positive integer (>200
>digit number).  For a given Zt, can you find Xn, where Xn is the first
>integer which is greater or equal to SQRT(Zt), i.e. Xn >= SQRT(Zt),
>which gives an integer Ym, which will satisfy the above hyperbolic
>equation? I can do it by testing the equation with each integer x
>greater than sqrt(Zt), but it could take million years to find Xn, if Zt
>is a large integer number.  Does anyone have a better solution?
>Thanks...

Firstly, the problem cannot be solved unless z is some power of 4 times
an odd integer.
Dividing out the multiples of 4; which correspond to multiples of 2 for
both x and y; leaves the problem for z odd - a solution of which is
x = (z+1)/2 and y = (z-1)/2.
>--
>Kind Regards,

>Ricky Lee
>Email: lricky@earthcorp.com

Alan Jones