# 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

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.
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