4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\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.