# For integers $a$ and $b \gt 0$, and $n^2$ a sum of two square integers, does this strategy find the largest integer $x | x^2 \lt n^2(a^2 + b^2)$?

Here is some background information on the problem I am trying to solve. I start with the following equation:

$n^2(a^2 + b^2) = x^2 + y^2$, where $n, a, b, x, y \in \mathbb Z$, and $a \ge b \gt 0$, $n \gt 0$, and $x \ge y \gt 0$.

For given values of $a$ and $b$ and some $n$, I need to find $x$ and $y$ such that $x$ is as large as possible (and $y$ as small as possible). The value of $n$ is up to me as long as allowable values are linear ($n = kn_0$). A naive approach is to use the distributive property to set $x = na$ and $y = nb$, but this causes $x$ and $y$ to grow at the same rate and doesn't guarantee $x$ is as large as possible.

I realized that if $n^2$ is the sum of two square integers (the length of the hypotenuse of a Pythagorean triangle), then I can use the Brahmagupta–Fibonacci identity to find values for $x$ and $y$ that are as good or better than using the distributive property:

$(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2$

$n^2 = c^2 + d^2$, where $c \gt d$

So for example, if $a = 2$, $b = 1$, and $n = 5$, then instead of

$5^2(2^2 + 1^2) = 10^2 + 5^2 = 125$, so that $x = 10$ and $y = 5$ we get

$(4^2 + 3^2)(2^2 + 1^2) = (4\cdot2 +3\cdot1)^2 + (4\cdot1 - 3\cdot2)^2 = 11^2 + (-2)^2 = 125$, so $x = 11$ and $y=2$

My question is, does this strategy always find $x$ to be the largest possible integer whose square is less than $n^2(a^2 + b^2)$, for $n$ a sum of two square integers?

Let $N = n^2(a^2+b^2)$ and consider its prime factorization. Let $p$ be a prime divisor of $N$. If $p\equiv 3\pmod4$, then necessarily $p^2|N$, $p|x$ and $p|y$ (and the factor comes from $p|n$). If $p\equiv 1\pmod 4$, find $u,v$ such that $u^2+v^2=p$. Let $k$ be the exponet of $p$ in $N$, i.e. $p^k||N$. Then $x+iy$ must be a multiple of $(u+iv)^r(u-iv)^{k-r}$ with $0\le r\le k$. This gives you $k+1$ choices for each uch $p$, and in fact the optimal choice may be influenced by the choices for other primes. (The case $p=2$ is left as an exercise). The number of candidates to test is then the product of the $k+1$, which may become quite large, but of course much, much smaller than $N$.
• I'm a little confused. If $n^2 = c^2 + d^2$, then for any prime factor $p$ of $n$, $p \equiv 1 \pmod 4$, (see Pythagorean triple: Elementary Properties - "All prime factors of $c$ are primes of the form $4n + 1$"), so how can there be a factor of $p \equiv 3 \pmod 4$ coming from $n$? – hatch22 Oct 4 '12 at 18:45