# Sum of two squares proof

Find two pairs of relatively prime positive integers $(a,c)$ so that $a^2 + 5929 = c^2$. Can you find additional pairs with $gcd(a,c) > 1$?

What I know:

$gcd(a,c) = 1$ implies that there are some $x$ and $y$ such that $ax + cy = 1$. Since $a d$oes not divide $c$, I'm guessing that $a^2$ does not divide $c^2$ as well (need confirmation). In that case we then have $gcd(a^2, c^2) = 1$ so there are some x and y such that $a^2 x + c^2 y = 1$. I'm not 100% sure if that leads us anywhere but it does give an equation that is somewhat matching the question.

Let $c^2 = d$ We know that a number $d$ can be written as a sum of two squares if all its prime factors are either 2 or congruent to $1 (mod 4)$. We have $\sqrt(5929) = 77$. So we have that if $d = a^2 + 5929$, $d$ must be a product of distinct primes that are congruent to $1 (mod 4)$ or 2.

What am I missing from here that is keeping me back from answering this? It doesn't seem like a very difficult question yet I'm having trouble with it. Maybe its midnight speaking :(.

-
If $a$ does not divide $c$, it is true that $a^2$ does not divide $c^2$. What you need is (as you say) $gcd(a^2,c^2)=1$, which is stronger but is implied by $gcd(a,c)=1$. –  Ross Millikan Mar 17 '11 at 13:34

This is a naïve approach that comes to mind. Seeing squares on opposite sides of an equation makes me want to move one of them and use the difference of squares formula. That is, I can't resist rewriting that as $5929=(c-a)(c+a)$. This then leads to the approach of factoring $5929=7^211^2$, leading to all possible choices of $c-a$ and $c+a$. E.g., choosing $c+a=11^27$ and $c-a=7$ leads to $c=\frac{7}{2}(11^2+1)$ and $a=\frac{7}{2}(11^2-1)$. Analyzing all such possibilities is one way to find your answer.
By the way, choosing $c+a=11^2 7$ and $c−a=7$ cannot give relatively prime numbers, so you can understand there are not that many possibilities: you can only have (c-a, c+a) equals $(7^2, 11^2)$ or $(1, 7^2 11^2)$. –  Wok Mar 17 '11 at 9:35