System of Diophantine equations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:03:11Z http://mathoverflow.net/feeds/question/70208 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70208/system-of-diophantine-equations System of Diophantine equations unknown (yahoo) 2011-07-13T10:25:25Z 2011-07-14T05:26:11Z <p>$p + p' = m$</p> <p>$q - q' = n$</p> <p>$pp' = qq'$</p> <p>$(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$.</p> <p>Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently?</p> http://mathoverflow.net/questions/70208/system-of-diophantine-equations/70286#70286 Answer by Will Jagy for System of Diophantine equations Will Jagy 2011-07-14T02:53:54Z 2011-07-14T03:42:41Z <p>Since finding all possible expressions $$M^2 + N^2 = m^2 + n^2$$ will in fact give you a complete factorization of $m^2 + n^2,$ all you need to know is how to create all $(M,N)$ pairs from a complete prime factorization of $m^2 + n^2 = p_1 p_2 p_3 \ldots p_r q_1^2 q_2^2 \ldots q_s^2,$ where the $p_i \equiv 1 \pmod 4,$ while all $q_j \equiv 3 \pmod 4,$ and the labeled primes are not necessarily distinct. Each prime $p_i$ has essentially one representation as the sum of two squares, at least when positive and ordered. Then you just use $$(a^2 + b^2) (c^2 + d^2) = (a c + b d)^2 + ( a d - b c)^2$$ while putting in $\pm$ signs on $a,b,c,d$ and switching order. For each expression, you just multiply through by all the $q_j.$ The $q_j$ must, of course, appear as factors of $\gcd(m,n).$ </p> <p>The general method for any $x^2 + k y^2 = t,$ for some $k \geq 1,$ is the Hardy-Muskat-Williams algorithm, which is implemented in some CAS, sometimes correctly. Given any $p_i,$ the first task in solving $u^2 + v^2 = p_i$ is finding a square root of $-1 \pmod {p_i}.$ The rest of this is treated in <em>Editor's Corner: The Euclidean Algorithm Strikes Again</em> by Stan Wagon, M.A.A. Monthly,Vol. 97, No. 2 (Feb., 1990), pp. 125-129. The first page can be seen at this <a href="http://www.jstor.org/pss/2323912" rel="nofollow">link</a>. However, the way I would do it is to take the integer with $w^2 \equiv -1 \pmod {p_i},$ or $w^2 + 1 = p_i t,$ write down the positive quadratic form $\langle p_i, 2 w, t \rangle$ and keep track of each step as I reduce it to $\langle 1,0,1 \rangle,$ reversing steps to find a representation $u^2 + v^2 = p_i.$ Although, as I think of it, I actually do the whole thing by matrix multiplication anyway.</p> <p>Meanwhile, there is a very nice note on using multiple expressions as the sums of two squares to factor a number, in the M. A. A. Monthly, December 2009, pages 928-931, <em>A Note on Euler's Factoring Problem</em> by John Brillhart.</p> <p><a href="http://mathoverflow.net/questions/57981/" rel="nofollow">http://mathoverflow.net/questions/57981/</a></p> http://mathoverflow.net/questions/70208/system-of-diophantine-equations/70295#70295 Answer by Victor Miller for System of Diophantine equations Victor Miller 2011-07-14T04:52:51Z 2011-07-14T05:26:11Z <p>Thanks to Noam Elkies for telling me to post my one-liner to solve this in gp (this dates from around 1993):</p> <p>fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]</p> <p>What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 &lt; a &lt; (p-1)/2$ satisfies $a^2 = -1 \bmod{p}$ if you run the continued fraction algorithm for $a/p$ "half-way" to get the convergent $r/s$ then $r^2 + s^2 = p$. What the above one-liner does is to set up the lattice $$\pmatrix {a&amp;p \cr 1 &amp; 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$.</p>