🚀 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

 (x-y)(x+y)=z , if x-y=1 then z=x+y -> y+1+y=z  and 2y=z-1 and y=(z-1)/2.
(Ref. Euler and Fermat: "Every prime is The difference of two squares".

Tapio

Paul Nulsen wrote in message ...
|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?
(snip)
|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).

(snip)

|Paul Nulsen
|

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

asj@maths.uq.edu.au (Alan Jones) writes:


>Firstly, the problem cannot be solved unless z is some power of 4 times
>an odd integer.

Mea Culpa. z is either odd or a multiple of four.
(non unique) solutions are (z/4 + 1) and (z/4 -1) in the latter case.

> z odd - a solution of which is
>x = (z+1)/2 and y = (z-1)/2.
>>--
 Alan Jones