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?
$\begingroup$
$\endgroup$
1
asked Feb 28, 2013 at 22:13
-
$\begingroup$ 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... $\endgroup$– xavierm02Feb 28, 2013 at 22:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Feb 28, 2013 at 22:17
-
$\begingroup$ 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? $\endgroup$ Feb 28, 2013 at 22:21
-
$\begingroup$ 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. $\endgroup$ Feb 28, 2013 at 22:30
-
$\begingroup$ The current champion, General Number Field Sieve, is in fact a remote descendant of the Fermat's Method, and you could say that it actually evolved in the process of "optimizing search procedures". $\endgroup$ Aug 11, 2020 at 22:56
$\begingroup$
$\endgroup$
1
There is also the trivial case. Suppose $d=2n+1$, then it is the difference between the squares $n$ and $n+1$.
-
$\begingroup$ Which he already knows. His $(d-1)/2$ and $(d+1)/2$ are your $n$ and $n+1$. $\endgroup$ Feb 28, 2013 at 22:24