# Is there an algorithm for finding squares with a given difference?

Consider an odd number d. Being odd, it can always be expressed as the difference of two squares. The number of ways that it can be expressed as the difference of two squares depends on how many factors it has. For example, d can always be expressed as the difference of the squares of (d+1)/2 and (d-1)/2, and if it is composite (d=ab; it may be factorable in many distinct ways), then the squares of the numbers (a+b)/2 and (a-b)/2 have the difference d. Note that if d is prime, then the only set of numbers whose squares differ by d are (d+1)/2 and (d-1)/2; if d is a semiprime (d=pq) then the only additional set of numbers whose squares differ by d are (p+q)/2 and (p-q)/2. Odd numbers with more than two prime factors will in general be expressable as the difference of multiple pairs of squares (cubes of primes are one exception; I don't know whether there are others). If we know the factors of d, we can generate all of the the pairs of numbers whose squares differ by d. My question is, if we do not know the factors of d, are there algorithms for generating pairs of numbers whose squares differ by d?

-
I guess you could chose $n$ so that $2n+1\ge d$ and then try all the pairs $(a,b)$ that respect $a<b<n$. That'd be $O(n^2)$ though... – xavierm02 Feb 28 '13 at 22:27

Apart from the trivial representation that you mentioned, the answer is basically no.

For if we know numbers $x$ and $y$ such that $x^2-y^2=d$, then since $x^2-y^2=(x+y)(x-y)$, we know a pair of factors of $d$.

Of course if we know a partial factorization of $d$, for example $d=3\cdot 5\cdot m$ where we do not know a factorization of $m$, we can find some non-trivial representations of $d$ as a difference of two squares.

-
I understand that after we identify the squares whose difference is d, we can discover factors of d; my question is whether there are methods (such as by making and refining approximations) that can lead us to those squares? – Keith Backman Feb 28 '13 at 22:21
The problem is equivalent to factorization, and in an immediate way. So yes, there are algorithms, the many very clever factorization algorithms. Some work was done in optimizing search procedures, in connection with the Fermat Method of Factorization. But the results are far less efficient than more sophisticated factorization algorithms. – André Nicolas Feb 28 '13 at 22:30

There is also the trivial case. Suppose $d=2n+1$, then it is the difference between the squares $n$ and $n+1$.

-
Which he already knows. His $(d-1)/2$ and $(d+1)/2$ are your $n$ and $n+1$. – xavierm02 Feb 28 '13 at 22:24