🚀 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?

This does not solve your problem, but it might save some wasted time:

Since x^2 - y^2 = (x + y)(x - y), any solution gives a factorization of z.
So, if z = p q with p > q, then x = (p + q)/2 and y = (p - q)/2 give a
solution (not necessarily integral).

Now if z has only one factor of 2, ie z = 2 a, with a odd, then exactly one
of p and q is always even and the other one must be odd, which means that
both x and y given above have to be half integral.  In other words, there
can be no integral solutions for x and y in this case, so you can forget it.

There are always some solutions if z is odd [eg x = (z + 1)/2, y = (z - 1)/2]
or if z is a multiple of 4 [eg x = z/4 + 1, y = z/4 - 1].  Your problem
reduces to finding the factorization z = p q that minimises p - q.  If you
already have a complete factorization of z, this should be straightforward.
However, since factorization is notoriously difficult, I doubt that it will
help you much.

Paul Nulsen