<s>[INST] Elementary number theory proof without contradiction 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.
 [/INST] 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$.
</s>