# System of Diophantine equations

$p + p' = m$

$q - q' = n$

$pp' = qq'$

$(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$.

Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently?

-
It's a finite problem, so exhaustive search ought to work. Perhaps you're looking for a certain level of efficiency? –  Gerry Myerson Jul 13 '11 at 11:47
The mod 4 conditions amount to saying that n is even and m is odd. The system boils down to solving p(m-p)=q(q-n), which can be rewritten as p^2-pm+q^2-qn=0, which can be rewritten as (m-2p)^2 + (n-2q)^2 = m^2 + n^2, which can be rewritten as M^2 + N^2 = m^2 + n^2 with M odd and N even. So you're basically asking for different ways to write an odd number as the sum of two squares. –  Barry Cipra Jul 13 '11 at 12:26
@Barry interesting could you elaborate how to find such representations? –  user16007 Jul 13 '11 at 21:36

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

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 Editor's Corner: The Euclidean Algorithm Strikes Again by Stan Wagon, M.A.A. Monthly,Vol. 97, No. 2 (Feb., 1990), pp. 125-129. The first page can be seen at this link. 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.

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, A Note on Euler's Factoring Problem by John Brillhart.

Testing whether an integer is the sum of two squares

-

Thanks to Noam Elkies for telling me to post my one-liner to solve this in gp (this dates from around 1993):

fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]

What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 < a < (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&p \cr 1 & 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$.

-
Victor, I edited your matrix and hope I got it right. –  Gerry Myerson Jul 14 '11 at 5:03
@Victor what is gp? –  user16007 Jul 14 '11 at 5:08
This doesn't look right because the determinant of the matrix should be $\pm p$. The bottom row should be $(1,0)$, not $(p,1)$. Note that gp uses the lattice generated by the columns of a matrix, not the rows. –  Noam D. Elkies Jul 14 '11 at 5:09
@Noam: thanks. I was having problems with mathjax and matrices. Gerry fixed it for me. –  Victor Miller Jul 14 '11 at 13:13
@unknown: gp is the computation language which comes with the Pari library for doing number theory. –  Victor Miller Jul 14 '11 at 13:14