# Prove that if $\gcd(a,b) = 1$, then $\gcd(ab,a^2+b^2)=1.$

I was reading a Proof that stated

Since $\gcd(a, b) = 1$, it follows that $\gcd(ab, a^2 + b^2) = 1$.

I can't figure out why this statement is true. I tried to factor $ab$ and $a^2+b^2$, but I don't think that you can really reduce $a^2$ and $b^2$ because it's just addition. I'm not really sure how to go about this. Any help?

I always prefer Bézout's Identity proofs.

Lemma 1: If $\gcd(c,d)=1$ then $\gcd(c,ck+d)=1$ for any $k$.

Proof: If $cx+dy=1$, then $c(x-ky)+(ck+d)y=1$.

Lemma 2: If $\gcd(c_1,d)=1$ and $\gcd(c_2,d)=1$ then $\gcd(c_1c_2,d)=1$.

Proof: Solve $c_1x_1+dy_1=1$ and $c_2x_2+dy_2=1$. Multiplying, and you get:

$$c_1c_2(x_1y_1)+d(y_2c_1x_1+y_1c_2x_2+dy_1y_2)=1$$

Theorem: If $\gcd(a,b)=1$ then $\gcd(ab,a^2+b^2)=1$.

Proof: Lemma 2 implies that $\gcd(a,b^2)=1$. Lemma 1 implies that $\gcd(a,a^2+b^2)=1$.

Likewise, we get that $\gcd(b,a^2+b^2)=1$.

Then, by Lemma 2, we have that $\gcd(ab,a^2+b^2)=1$.

Let $d=gcd(ab,a^2+b^2)$. Then $d\mid ab$ and $d\mid a^2+b^2$. For a prime divisor $p\mid d$ with $p\mid ab$ we have $p\mid a$ or $p\mid b$. Suppose that $p\mid a$. Then $p\mid a^2$, and because $p\mid a^2+b^2$ we also get $p\mid b^2$. Similarly $p\mid b$ implies that $p\mid a^2$. Hence we obtain $$p\mid gcd(a^2,b^2)=gcd(a,b)=1.$$ For the last step, see this duplicate: Prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$.

• If $d=p\cdot q$ then $d|ab$ doesn't imply that $d|a$ or $d|b$ – arberavdullahu Aug 13 '17 at 19:39
• @arberavdullahu True but it should work if one considers a single prime factor of $d$. – Evariste Aug 13 '17 at 19:41
• @arberavdullahu Yes, of course, you are right. – Dietrich Burde Aug 13 '17 at 19:46

Remark: every natural number greater than $1$, have a prime factor.

Euclid's Lemma: Let $a$ and $b$ to be integers and let $p$ to be a prime number.

If $p \mid ab$ then $p \mid a$ or $p \mid b$.

Lemma(2): Let $b$ to be an integer and let $p$ to be a prime number.

If $p \mid b^2$ then $p \mid b$.

Suppose on contrary that $\gcd(ab, a^2+b^2) \geq 1$, so by the above remark it must have a prime factor $p$.

Notice that $p \mid ab$, without loss of generality by the Euclid's lemma we can assume that $p \mid a$, so we have: $p \mid a^2$.

On the otherhand $p \mid a^2+b^2$, so we have $p \mid (a^2+b^2)-a^2$, i.e. $p \mid b^2$, and by the lemma(2) then $p \mid b$.

So we have: $p \mid a$ and $p \mid b$; but notice that, it is an obvious contradiction with the assumption that $\gcd(a,b)=1$.

Set $d:=gcd(ab,a^2+b^2)$ and assume $d\neq 1.$ This means that there exists a prime $p$ with $$p|d|ab,$$which impliess $p|a$ or $p|b.$ Wlog we can say $p|a.$ Using this and $$p|d|a^2+b^2$$implies $p|b^2$ and therefore $p|b$, because p is prime. But this means that $p$ is a number at least $2$ and divides $a,b.$ But this is a contradiction to $gcd(a,b)=1.$

If $$p$$ is a prime and $$p|ab, p|(a^2+b^2)$$ then $$p|(a^2+2ab+b^2)$$, so $$p|a+b$$.

But then $$p|ab+b^2$$ and $$p|ab+a^2$$, so $$p|b^2$$, $$p|a^2$$, implying $$p|MCD(a^2,b^2)=1$$, contradiction.

Then $$p$$ doesn't exist, and the problem is solved!