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?
 A: 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$.
A: 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$.
A: 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$.
A: Set $d:=gcd(ab,a^2+b^2)$ and assume $d\neq 1.$ This means that there exists a prime $p$ with \begin{equation}p|d|ab,
\end{equation}which implies $p|a$ or $p|b.$ Wlog we can say $p|a.$ Using this and
\begin{equation}p|d|a^2+b^2
\end{equation}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.$
A: 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!
