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 am trying to prove that, given positive integers $a, b, c$ such that $a + b = c^2$, $\gcd(a, c) = \gcd(b, c)$. I am getting a bit stuck.

I have written down that $(a, c) = ra + sc$ and $(b, c) = xb + yc$ for some integers $r, s, x, y$. I am now trying to see how I can manipulate these expressions considering that $a + b = c^2$ in order to work towards $ra + sc = xb + yc$ which means $(a, c) = (b, c)$. Am I starting off correctly, or am I missing something important? Any advice would help.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

Let $d=\gcd(a,c)$ and $e=\gcd(b,c)$. Then $d$ divides $a$ and $d$ divides $c$, so $d$ divides $c^2$. It follows that $d$ divides $c^2-a$, that is, $d$ divides $b$. Since $d$ also divides $c$, it follows that $d$ divides $b$ and $c$, so $d$ divides $e$.

Similarly, $e$ divides $d$. It follows that $d=e$.

share|improve this answer

I don't see a way to proceed using the approach you suggest - this doesn't mean that there isn't one (it's often a good method to work through). But I don't see it yet. But you can directly show that the same primes to the same powers divide each:

Consider a prime $p$. Suppose that $p^\beta \mid \mid \gcd(a,c)$, so that in particular $p^\beta \mid c^2 - a = b$. And so $p^\beta | a$.

Suppose now that $p^\alpha \mid \mid a$. Then we know that $\alpha \geq \beta$ from this argument. Reversing the roles of $a$ and $b$ in the same argument shows that $\beta \geq \alpha$. Thus $\alpha = \beta$, and so the same primes to the same powers maximally divide $\gcd(a,c)$ and $\gcd(b,c)$.

Further, it seems this argument generalizes to cases that look like $a + b = c^n$ for any $n \geq 1$.

share|improve this answer

Hint $\ \ (b,c) = (c^2-a,c) = (-a,c),\:$ since $\:(n,c) = (n{\rm\: mod\:} c, c)\ $ by Euclid.

share|improve this answer
1  
Math Gems! I haven't seen you for a while. Welcome back to MSE! –  mixedmath Jan 16 '13 at 4:15

Here is essentially André Nicholas's answer in a different form.

Borrowing the proof style and structure and properties $(0)$ and $(1)$ from another answer of mine (http://math.stackexchange.com/a/451278/11994), the original statement translates to $$\langle \forall d :: d|a \land d|c \;\equiv\; d|b \land d|c \rangle$$ or equivalently (by extracting the common conjunct) $$\langle \forall d : d|c : d|a \equiv d|b \rangle$$ which we must prove under the assumption $\;a+b=c^2\;$.

This is easily done, for any $\;d\;$, as follows: \begin{align} & d|a \;\equiv\; d|b \\ \Leftarrow & \;\;\;\;\;\text{"property of divisibility: numbers are equally divisible if their sum is} \\ & \;\;\;\;\;\phantom{"}\text{-- suggested by our assumption"} \\ & d|(a+b) \\ \equiv& \;\;\;\;\;\text{"our assumption"} \\ & d|c^2 \\ \Leftarrow& \;\;\;\;\;\text{"property of divisibility: a divisor of a factor also divides the product"} \\ & d|c \\ \end{align} This completes the proof, and the last step shows that the assumption can be generalized to $\;a+b=c\cdot n\;$ for any integer $\;n\;$, or in other words, $\;c|(a+b)\;$.

share|improve this answer

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.