Differences of squares - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:24:29Z http://mathoverflow.net/feeds/question/39548 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39548/differences-of-squares Differences of squares Charles 2010-09-21T23:06:58Z 2010-09-22T00:17:06Z <p>Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem is weakened to searching for $a\neq b$ with $a^2\equiv b^2\pmod N$ the problem is still hard (though not as hard), since enough congruences could be used to factor $N$ with Dixon's method or any of its modern versions (in particular, the number field sieve).</p> <p>So I am curious about the difficulty of these weak versions of the problem. Are any of these easier than finding relations with the NFS?</p> <ol> <li><p><em>Weak form.</em> Given $N$, $k$, and a factoring oracle, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.</p></li> <li><p><em>Semi-weak form.</em> Given $N$, $k$, and the complete factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.</p></li> <li><p><em>Strong form.</em> Given $N$, $k$, and a partial factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.</p></li> </ol> http://mathoverflow.net/questions/39548/differences-of-squares/39553#39553 Answer by Micah Milinovich for Differences of squares Micah Milinovich 2010-09-21T23:27:21Z 2010-09-21T23:27:21Z <p>Here is a simple way to find <em>one</em> representation of $N$ as a difference of two squares.</p> <p>No integer $N\equiv 2 \text{ mod } 4$ is a difference of squares.</p> <p>If $N$ is odd, then $$N= (\frac{N+1}{2})^2 - (\frac{N-1}{2})^2.$$ </p> <p>If $4|N$, then $$N=(\frac{N}{4}+1)^2 - (\frac{N}{4}-1)^2.$$</p> http://mathoverflow.net/questions/39548/differences-of-squares/39557#39557 Answer by Gerry Myerson for Differences of squares Gerry Myerson 2010-09-21T23:44:32Z 2010-09-22T00:17:06Z <p>If you know any factors of $N$, it's easy to find non-trivial solutions of $a^2\equiv b^2\pmod N$. If $m$ and $n$ are (relatively prime) factors of $N$, then given any $a$, take $b$ to solve $b\equiv a\pmod m$, $b\equiv-a\pmod n$. </p> <p>EDIT: A bit careless of me, let's try again. If $N$ is odd and $N=mn$ is non-trivial with $\gcd(m,n)=1$, then the construction above, with $\gcd(a,N)=1$, gives a non-trivial solution of $a^2\equiv b^2\pmod N$. </p> http://mathoverflow.net/questions/39548/differences-of-squares/39558#39558 Answer by Nick S for Differences of squares Nick S 2010-09-21T23:44:54Z 2010-09-21T23:50:59Z <p>I think he is more interested in how many ways can one number be written as a difference of squares.</p> <p>The solution to the semiweak form is actually simple, since $a+b$ and $a-b$ have the same parity.</p> <p>If $N$ is odd, then as long as $N$ has at least 2k divisors (which can easely be seen from the factorisation of $N$) you can simply write $k$ different pairs $(d,N/d)$ with $d$ smaller than $N/d$ and solve </p> <p>$$a-b= d \,;\, a+b= N/d \,.$$</p> <p>If $N\equiv 2 \text{mod} 4$ there is no solution as noted above.</p> <p>If $N\equiv 0 \text{mod} 4$ then you do the same trick for $N/4$: as long as $N/4$ has at least 2k divisors you can simply write $k$ different pairs $(d,N/4d)$ with $d$ smaller than $N/4d$ and solve </p> <p>$$a-b= 2d \,;\, a+b= N/2d \,.$$</p> <p>Edit: Same thing works for the strong form, as long as the partial factorisation of $N$ is "big" enough: i.e. it allows us to find k distinct pairs pairs $(d,N/d)$ of divisors of same parity with $d$ smaller than $N/d$. </p>