# Prove $\gcd(a,b)=\gcd(a+b,\operatorname{lcm}(a,b))$

Any ideas on how to prove this equality? I tried various methods, using properties of gcd and lcd, but I can't prove it.

• @RSerrao : You could make the same correction in your notation that I made when I edited the question. $\qquad$ – Michael Hardy Nov 12 '16 at 1:25

First we prove that if $\gcd(u,v)=1$ then $\gcd(u+v,uv)=1$

Proof:

If $\gcd(u+v,uv)\neq 1$ there is a prime $p$ such is $p|u+v$ and $p|uv$

Now if $p|uv$ then $p|u$ or $p|v$. Without loss of generality we can assume $p|u$.

Now from $p|u+v$ and $p|u$ we get $p|v$. So $p$ is a common factor of $u$ and $v$. Contradiction.

Going back to the problem:

Assume $d=\gcd(a,b)$ we have $a=du$ and $b=dv$ with $\gcd(u,v)=1$

Also we have $\text{lcm}(a,b)=duv$

So on the right side we have:

$\gcd(d(u+v),duv)=d\gcd(u+v,uv)=d$

Which was to be proved.

Below are a few proofs. We use notation $\ (x,y) := \gcd(x,y)\$ and $\ [x,y] := {\rm lcm}(x,y)$

First, recalling that gcd distributes over lcm we obtain

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

Or, cancelling $\,(a,b)\,$ reduces to 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])$$

Or, 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$$

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

You may want to try and prove first that

$\operatorname{gcd}(a, b) = \operatorname{gcd}(b, a - b)$

This identity should be enough to get you rolling. You will just have to be able to use it correctly.

Alternatively, try this approach. Suppose $d$ is the gcd of $a$ and $b$. Show it divides $a+b$ and $\operatorname {lcm}(a, b)$.

Then suppose $d'$ is the gcd of $a+b$ and $\operatorname {lcm}(a, b)$. Show $d'$ divides both $a$ and $b$. Hence $d$ divides $d'$ which divides $d$, meaning they must be equal.

Let gcd(a,b)=d. a=ds , b=de . a+b=d(e+s). lcm(a,b)=ab/d=des. Assume x greater than d divides des,d(e+s). By the first it divides one of e and s. But if it divides one, it must divide both by the second. But hten dx is the gcd a contradiction.