1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – hatch22 Oct 4 '12 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.