3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Oct 23, 2016 at 4:42
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Oct 23, 2016 at 4:45
  • $\begingroup$ $1 \not\in PRIMES$ so there is no point in stating that $p \neq 1$ when we already said that $p$ is prime. $\endgroup$
    – Hauleth
    Oct 23, 2016 at 10:32

4 Answers 4

5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$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

$\endgroup$
1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.