$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$.

318 Views Asked by At

If $a,b\in \mathbb{Z}$ then: $$\gcd(a,b)=1 \iff \gcd(a+b,ab)=1$$

Let $p$ be a prime number.

Let $\gcd(a,b)=1$, and $p | a+b,p|ab$. $p|ab \implies p|a \ \text{or}\ p|b$. WLOG let $p|a$, then $p|a+b$ and $p|a$ implies $p|b$. But we have $\gcd(a,b)=1$ a contradiction. Thus We must have $gcd(a+b,ab)=1$.

Conversely let $\gcd(a+b,ab)=1$, $p|a$ and $p|b$ then $p|a+b$ and $p|ab$ a contradiction again. Thus we must have $\gcd(a,b)=1$.

Is the proof correct?

2

There are 2 best solutions below

1
On

Your proof is perfectly correct. There is nothing to add.

Your proof works also in this implication: Let $m,n\in \mathbb{Z}$, then

$$ \gcd(ma+nb,ab)=1\implies \gcd(a,b)=1$$

and as Heterbij pointed out, the other implication doesn't work.

0
On

You basic reasoning is okay, but as written it is logically sloppy. Here is what it should be like:


Take any integers $a,b$.

If $\gcd(a,b) = 1$: For every prime $p$ we cannot have $p \mid a+b , ab$, otherwise from $p \mid ab$ we get $p \mid a$ or $p \mid b$, and so WLOG $p \mid a$, and from $p \mid a,a+b$ we get $p \mid b$ and so $\gcd(a,b) \ne 1$. Therefore $\gcd(a+b,ab) = 1$.

If $\gcd(a+b,ab) = 1$: For every prime $p$ we cannot have $p \mid a,b$, otherwise we get $p \mid a+b,ab$ and so $\gcd(a+b,ab) \ne 1$. Therefore $\gcd(a,b) = 1$.


Note the key difference between your attempt and my version: The prime $p$ is separately quantified in each case. You cannot use the same prime $p$ in both the forward and reverse direction, because you want to insert the conclusion in each case, namely the statement beginning with "therefore" in my version, which requires the $p$ to be quantified over all primes.

Incidentally, there is another approach:


$\gcd(a+b,ab) = \gcd(a+b,ab-b(a+b)) = \gcd(a+b,b^2)$

$\gcd(a,b) = \gcd(a+b,b) \mid \gcd(a+b,b^2)$. Thus if $\gcd(a+b,ab) = 1$ then $\gcd(a,b) = 1$.

$\gcd(a+b,b^2) \mid \gcd(a+b,b)^2 = \gcd(a,b)^2$. Thus if $\gcd(a,b) = 1$ then $\gcd(a+b,ab) = 1$.