# Proving $\gcd(a, c) = \gcd(b, c)$ for $a + b = c^2$

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.

-

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

-

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

-

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

-
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)\;$.

-