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.

I was reasonably certain I've seen this before, but I was wondering how to solve the Diophantine equation

$$a^2+b^2=c^2+d^2$$

I tried a web search and found nothing on this one. I'm trying to avoid another library trip to a less than local library (maybe I should have taken better notes on that chapter...).

I'm not quite sure how to handle this one. The only thing I can figure out with this equation, if I remember correctly, is that the sum on either side may only contain prime factors of 2 or odd primes congruent to 1 mod 4. And if I don't want a and b equal to c and d, the sum can't be prime as I believe a prime congruent to 1 mod 4 can be represented as the sum of 2 squares in exactly one way. But that doesn't give me any insight into actually solving this problem.

share|improve this question
1  
Write it as $a^2 - c^2 = d^2 - b^2$. –  Qiaochu Yuan Jun 4 '12 at 3:49
    
@QiaochuYuan: What does that give. I also thought of the same thing, but couldn't get far enough. –  user9413 Jun 4 '12 at 3:52
    
I’ll add just a little and remark that it has something to do with the number of primes congruent to 1 modulo 4 that appear in the number. For instance, $65=64+1=49+16$. –  Lubin Jun 4 '12 at 3:54
    
Follow Lubin's hint you will find the solution if you think the problem in the ring $\mathbb{Z}[i]$. The next example will be $85$. –  Joy-Joy Jun 4 '12 at 4:15
add comment

4 Answers 4

up vote 3 down vote accepted

Essentially you ask for a parametrization of the quadric $V(a^2+b^2=c^2+d^2)$. There is a general geometric method how to do that, which you can find here. On page 13, this example is discussed: Solutions of $a^2+b^2=c^2+d^2$ are parametrized by

$(a,b,c,d) = (p r + q s , q r - p s , p r - q s , p s + q r),$

where $p,q,r,s$ are arbitrary. But one can also derive this via complex numbers (similar to the complex numbers solution of Pythagorean triples): Let $u = p + qi$, $v = r + si \in \mathbb{C}$. Then we have

$$|u \overline{v}| = |u| |\overline{v}| = |u| |v| = |u v|.$$

Square both sides, and compute the norms of the products explicitly. This gives you

$$(p r + q s)^2 + (q r - p s)^2 = (p r - q s)^2 + (p s + q r)^2.$$

share|improve this answer
    
+1 do you think that the parametrization of the quadric, or some extension to higher powers, could help answering my questions on Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$? and/or "Number of Decompositions into $k$ Powers of $p$"-Counting Functions? I'd be ever so happy, if you could have a look... –  draks ... Jun 4 '12 at 12:55
    
Bah! I should have figured this out. I think this is what Wolfram apparently calls the Fibonacci Identity, similar to Andre's Brahmagupta Identity above. Wolfram has it written as $(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2$. I believe the book wrote them separately. With the same variables, that yields $(ac+bd)^2+(bc-ad)^2=(ac-bd)^2+(bc+ad)^2$, which I think is equivalent to what you have. –  Mike Jun 4 '12 at 20:37
add comment

Let $N$ be a positive integer with prime power factorization $$N=2^a \prod_{i=1}^m p_i^{b_i}\prod_{j=1}^n q_j^{c_j},$$ where the $p_i$ are distinct primes congruent to $1$ modulo $4$, and the $q_j$ are distinct primes congruent to $-1$ modulo $4$. (We allow $a$ to be $0$, and $m$ or $n$ or both could be $0$.)

If at least one $c_j$ is odd, then $N$ has no representations as a sum of two squares. If all the $c_j$ are even, then the number of representations of $N$ as a sum of two squares is equal to $f(N)$, where $$f(N)=4\prod_{i=1}^m (b_i+1).$$ In this formula, in counting representations, order matters, and we allow the possibility of using negative integers.

If we want, for example, the representation $5=1^2+2^2$ to count as essentially the same as the representation $5=2^2+1^2$, and we do not want to allow negative integers, things get somewhat more complicated. Let $g(N)$ be the number of representations of $N$ as a sum of two non-negative squares, where order does not matter.

If $f(N)$ as defined above is divisible by $8$, then $g(N)=f(N)/8$.

If $f(N)$ as defined above is not divisible by $8$, then $g(N)=(f(N)+4)/8$.

The above formula gives a partial answer to your question, in that it tells us the number of solutions of the equation $a^2+b^2=c^2+d^2=N$, where order does not matter,and we allow only non-negative integers in the representation.

Your question also asks how to actually produce the solutions. The difficult part is to find representations of the $p_i$ as a sum of two squares. As you mentioned, there is, for any prime $p_i$ congruent to $1$ modulo $4$, essentially only one such representation. There are reasonably good algorithms available for producing the representation of such primes.

Once we have representations for the appropriate primes, we can obtain representations for products by repeatedly using the Brahmagupta Identity $$(s^2+t^2)(u^2+v^2)=(su+tv)^2+ (sv-tu)^2.$$ Here is a simple example. We have $13=2^2+3^2$ and $17=1^2+4^2$. So taking $s=2$, $t=3$, $u=1$, and $v=4$ we get $221=13\cdot 17= 14^2 + 5^2$.

Another essentially equivalent approach is to factor $N$ as a product of Gaussian primes. Once we have that, we can easily produce all representations of $N$ as a sum of two squares.

share|improve this answer
1  
Nicolas: It's Brahmagupta identity not Bahmagupta identity –  user9413 Jun 4 '12 at 4:44
    
@Chandrasekhar: Thanks for telling me about the typo. Fixed. –  André Nicolas Jun 4 '12 at 4:52
    
Always welcome. –  user9413 Jun 4 '12 at 5:41
    
Might I ask where that formula for f(N) comes from? –  Mike Jan 10 '13 at 17:17
    
It can be proved without Gaussian integers, but the structurally nice way to do it is to use the fact that primes of the form $4k+1$ split in essentially one way in the Gaussian integers, and primes of the form $4k+3$ don't split. –  André Nicolas Jan 11 '13 at 20:29
add comment

This equation is quite symmetrical so formulas making too much can be written: So for the equation:

$X^2+Y^2=Z^2+R^2$

solution:

$X=a(p^2+s^2)$

$Y=b(p^2+s^2)$

$Z=a(p^2-s^2)+2psb$

$R=2psa+(s^2-p^2)b$

solution:

$X=p^2-2(a-2b)ps+(2a^2-4ab+3b^2)s^2$

$Y=2p^2-4(a-b)ps+(4a^2-6ab+2b^2)s^2$

$Z=2p^2-2(a-2b)ps+2(b^2-a^2)s^2$

$R=p^2-2(3a-2b)ps+(4a^2-8ab+3b^2)s^2$

solution:

$X=p^2+2(a-2b)ps+(10a^2-4ab-5b^2)s^2$

$Y=2p^2+4(a+b)ps+(20a^2-14ab+2b^2)s^2$

$Z=-2p^2+2(a-2b)ps+(22a^2-16ab-2b^2)s^2$

$R=p^2+2(7a-2b)ps+(4a^2+8ab-5b^2)s^2$

solution:

$X=2(a+b)p^2+2(a+b)ps+(5a-4b)s^2$

$Y=2((2a-b)p^2+2(a+b)ps+(5a-b)s^2)$

$Z=2((a+b)p^2+(7a-2b)ps+(a+b)s^2)$

$R=2(b-2a)p^2+2(a+b)ps+(11a-4b)s^2$

solution:

$X=2(b-a)p^2+2(a-b)ps-as^2$

$Y=2((b-2a)p^2+2(a-b)ps+(b-a)s^2)$

$Z=2((b-a)p^2+(3a-2b)ps-(a-b)s^2)$

$R=2(b-2a)p^2+2(a-b)ps+as^2$

solution:

$X=(p^2-s^2)b^2+a^2s^2$

$Y=b^2(p-s)^2-2abs^2+a^2s^2$

$Z=b^2(p-s)^2+2abps-a^2s^2$

$R=s^2(a-b)^2+2abps-p^2b^2$

number $a,b,p,s$ integers and sets us, and may be of any sign.

share|improve this answer
add comment

You can write a similar equation and solutions:

$a^2+ac+c^2=x^2+xy+y^2$

Solutions have the form:

$a=q^2+k^2-p^2+kq$

$c=q^2+k^2+2p^2+kq-3pk-3pq$

$x=q^2-2k^2-p^2+3pk-2qk$

$y=k^2-2q^2-p^2+3pq-2qk$

more:

$a=(b-k)p^2+2(3b-2k)ps+(5b-7k)s^2$

$c=b(p^2-s^2)$

$x=bp^2+2(3b-2k)ps+(5b-8k)s^2$

$y=(b-k)p^2-2kps-(b-3k)s^2$

more:

$a=-(k+b)p^2+2(3b+k)ps+(7b-13k)s^2$

$c=2b(p^2-s^2)$

$x=(k-b)p^2+2(3b+k)ps+(7b-15k)s^2$

$y=-(k+b)p^2+6(k-b)ps+(7k-5b)s^2$

share|improve this answer
add comment

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.