Elementary number theory proof without contradiction

Question

Question: suppose $a, b, c$ are integers and $\gcd(a,b) = 1$. Prove that if $c|(a^2+b^2)$ then $\gcd(a,c) = gcd(b,c) = 1$.

Prove by contradiction (naive approach) : assume $p \in PRIMES$ and $\ne1$ such that: $p|a$ and $p|c$. Since $c|(a^2+b^2)$ then $p|(a^2+b^2) \Rightarrow p|b^2$ (because $p|a$ which means $p|a^2$). Thus, as $p|b^2$ then $p|b$. It contradicts with the fact that: $\gcd(a, b) = 1$

My question is that is there another way to prove it? (preferably without contradiction).

Any help would be appreciated.

Answer 1

Suppose $a^2+b^2=kc$ and, as implied by $\text{gcd}(a,b)=1$, we have $ma+nb=1$ for some integers $m$ and $n$. Then $$ 1=m^2a^2+n^2b^2+2mnab. $$ Consider the RHS above: \begin{aligned} 1=\text{RHS}&=m^2(a^2+b^2)+(n^2-m^2)b^2+2mnab=c(km^2)+b[(n^2-m^2)b+2mna];\\ 1=\text{RHS}&=n^2(a^2+b^2)+(m^2-n^2)a^2+2mnab=c(kn^2)+a[(m^2-n^2)a+2mnb]. \end{aligned} Then, respectively, the two lines above prove $\text{gcd}(c,b)=1$ and $\text{gcd}(c,a)=1$.

Answer 2

$c\mid a^2\!+b^2\Rightarrow\,(c,a) = (c,a,a^2\!+b^2) = (c,a,b^2) = 1\,$ by $\,(a,b)=1\,\Rightarrow\,(a,b^2)=1\,$ by Euclid

Answer 3

Consider $p$, a prime or $1$, that divides both $b$ and $c$. It divides $c$ so it divides $a^2+b^2$. It divides $b$ so it divides $b^2$. Dividing $b^2$ and $a^2+b^2$, it divides their difference namely $a^2$. Dividing $a^2$, because it is prime or $1$, it divides $a$. Dividing $a$ and $b$ it divides $1$ their gcd. So $p=1$

Permuting $b$ and $c$ in the above we prove $(a,c)=1$ as well

Answer 4

The proof for this is simple:

$\gcd(a, b)$ $=$ $1$, therefore $\gcd(a + b, a, b) $=$ $1, similarity $\gcd(a^n + b^n, a, b) $=$ $1. Any prime $c$ dividing $a^n + b^n$, the $\gcd($c$, $b$, $a$) $=$ $1. Your question is when $n$ $=$ $2$.