# Let $a,b\in \mathbb{N^*}$. Prove that $\gcd(a+b,\operatorname{lcm})=\gcd(a,b)$. Is my proof correct?

Suppose $δ=(a+b,\operatorname{lcm}[a,b])$ and let it be that $δ\neq(a,b)$.

Then $\exists ε\big(ε=(a,b) \land ε\gt δ \big) \implies ε|a \land ε|b \implies ε|(a+b)$.

It is also true that $ε|\operatorname{lcm}[a,b]$.

By the two previous statements, we get that $ε|(a+b,\operatorname{lcm}[a,b])\implies ε|δ$. This is absurd since $ε>δ$.

Thus $δ=(a,b)$.

Is it correct? I wonder if i made errors during my logical analysis. Thanks in advance.

#### Solutions Collecting From Web of "Let $a,b\in \mathbb{N^*}$. Prove that $\gcd(a+b,\operatorname{lcm})=\gcd(a,b)$. Is my proof correct?"

Below are a few of many possible proofs.

Using the fact the gcd distributes over lcm we obtain

$$(a+b,[a,b]) = [(a+b,a),(a+b,b)] = [(b,a),(a,b)] = (a,b)$$

Cancelling $\,(a,b)\,$ we reduce to the case $\,(a,b) = 1\,$ so $\,ab = [a,b],\$ so by Euclid’s Lemma

$$\begin{eqnarray}(a+b,\color{#c00}a) = (b,a)= 1\\ (a+b,\color{#c00}b)=(a,b)=1\end{eqnarray}\ \Rightarrow\ 1 = (a+b,\color{#c00}{ab}) = (a+b,[a,b])$$

By the gcd * lcm law $\,(a,b)[a,b] = \color{#0a0}{ab}\,$ and gcd laws (associative, commutative, distributive)

$$(a,b)\ (a+b, [a,b])\ =\ (a(a+b),\,b(a+b),\, \color{#0a0}{ab})\ =\ (aa,\:bb,\:ab)\ =\ (a,b)^2$$

thus we deduce $\ (a+b,[a,b]) = (a,b)\$ by cancelling $\ (a,b)\neq 0$

Let $m=\gcd (a,b).$

We have $a=xm$ and $b=ym$ where $\gcd (x,y)=1.$ Then lcm $(a,b)=mxy.$ Proof: $\;mxy$ is a common multiple of $a, b.$ If $a|c$ then $c=az=mxz.$ And if also $b|c,$ we have $ym|mxz.$… So $y|xz,$ so $y|z$ …(because $\gcd (y,x)=1)$…Hence $z=yz’,$ implying $c=az=mxz=mxyz’.$

Therefore $$\gcd (a+b, \text {lcm} (a,b))=\gcd (xm+ym, xym)=m\cdot \gcd (x+y, xy).$$ Now if $p$ is prime and $p$ divides both $x+y$ and $xy$ then either $(p|x\land p|(x+y)$ or $(p|y\land p|(x+y).$ But either of these implies $(p|x\land p|y)$, which cannot be, as $p>1=\gcd (x,y).$ Therefore $\gcd (x+y,xy)=1$ and we are done.

How do you know that $\epsilon>\delta$? If I were to prove this, I would start by assuming without loss of generality that $\gcd(a,b)=1$. Then, find a contradiction when a prime $p$ divides both $a+b$ and $ab$.