Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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