5
$\begingroup$

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 :(.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Mar 17 '11 at 13:34
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ For relatively prime natural numbers, there are two solutions: (a, c) is (36, 85) or (2964, 2965). $\endgroup$ – Wok Mar 17 '11 at 9:32
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Wok Mar 17 '11 at 9:35
  • 1
    $\begingroup$ For non-coprime pairs, the same methods give (420,427), (264,275) and (0,77). $\endgroup$ – Henry Mar 17 '11 at 12:29

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.