# Let $a,b\in \mathbb{N^*}$. Prove that $\gcd(a+b,\operatorname{lcm}[a,b])=\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.

• What does $[a,b]$ mean in this context? – Aaron Jul 10 '16 at 0:00
• It's the least common multiple (lcm). How should i denote it in Latex? – Nikos Jul 10 '16 at 0:01
• You could do \operatorname{lcm}(a,b). – Aaron Jul 10 '16 at 0:03
• First, note that this isn't really a proof by contradiction: you didn't use the assumption $\epsilon>\delta$ anywhere, but rather you directly proved that $\epsilon\mid\delta$ and thus $\epsilon\le\delta$. (Perhaps you should justify why $\epsilon\mid[a,b]$.) Taking out the proof-by-contradiction wrapper will make it clearer. Second, you've managed to prove that $\epsilon\le\delta$, but you also need to prove $\epsilon\ge\delta$—perhaps by showing that $\delta$ divides both $a$ and $b$. – Greg Martin Jul 10 '16 at 0:18

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

• Since $ε=\gcd(a,b)$, then $ε|a \land ε|b$. It follows $ε|(a+b) \land ε|\operatorname{lcm}[a,b]$. So it must be that $ε>δ$. Right? – Nikos Jul 10 '16 at 0:11
• Doesn't that imply $\epsilon \leq \delta$? – Batominovski Jul 10 '16 at 0:14