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

• Yes. For example, all you need to do is to find a linear combination of $a^2+b^2$ and $a$ that sums to $1$, given some linear combination of $a$ and $b$ that sums to $1$. Then any factor of $a^2+b^2$ will be co-prime to $a$ and $b$. Oct 23, 2016 at 4:42
• Gcd (bc)|c and gcd (bc)|b so gcd (b,c)|c|a^2+b^2 so gcd (b,c) |a^2. So gcd (b,c)|gcd (a^2,b)=1. So gcd (b,c)=1. Oct 23, 2016 at 4:45
• $1 \not\in PRIMES$ so there is no point in stating that $p \neq 1$ when we already said that $p$ is prime. Oct 23, 2016 at 10:32

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

$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

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

• That's exactly the same as the proof in the question, so certainly not "another way". Oct 24, 2016 at 1:50

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