$\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$ Show that if $a$, $b$ are positive integers, then we have:
$\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$.
 A: Below are a few proofs. First, here's a couple from my sci.math post on 2001/11/10

For variety here is yet another using $\rm\ (a,b)\  [a,b]\ =\ \color{#c00}{ab}\ \ $ and basic gcd laws:
$\rm\quad (a,b)\ (a\!+\!b,\, [a,b])\, =\, (aa\!+\!ab,\, ab\!+\!bb,\, \color{#c00}{ab})\ =\ (aa,\,bb,\,ab)\, =\, (a,b)^2$
By the way, recall that the key identity in the second proof arose the other day in our discussion of Stieltjes $\rm\ 4\:n+3\ $ generalization of Euclid's proof of infinitely many primes. Here's a slicker proof:
Lemma $\rm\ \ (a\!+\!b,\,ab) = 1 \iff (a,b) = 1$
Proof $\rm\ \ \ (\color{#90f}a,b)^2 \color{#C00}{\large\subseteq} (a\!+\!b,\,ab) \color{#0a0}{\large \subseteq} (a,b)\ \ $ since, $ $ e.g. $\rm\ \ \color{#90f}{a^2} = a(a\!+\!b)-ab\color{#c00}{\large \in} (a\!+\!b,\,ab)$.
$\rm\ 1\in (a\!+\!b,\, ab) \color{#0a0}{\large\subseteq}(a,b)\Rightarrow 1\in (a,b).\:$ Conversely $\rm\ 1 \in (a,b) \Rightarrow 1 \in (a,b)^2\color{#c00}{\large\color{#c00}\subseteq} (a\!+\!b,\,ab)$
A: Another Dubuquesque attempt; for legibility, write $d=\gcd(a,b)$:
\begin{align*}
\gcd\Bigl(d(a+b), ab\Bigr) &= \gcd\Bigl(d(a+b), ab, ab\Bigr)\\
&=\gcd\Bigl(d(a+b),\ ab-a(a+b),\ ab-b(a+b)\Bigr)\\
&=\gcd\Bigl(d(a+b),\ a^2,\ b^2\Bigr)\\
&=\gcd\Bigl(d(a+b),\ \gcd(a^2,b^2)\Bigr)\\
&=\gcd\Bigl(d(a+b),\ \gcd(a,b)^2\Bigr)\\
&=\gcd\Bigl(d(a+b),\ d^2\Bigr)\\
&= d\gcd\Bigl(a+b,d\Bigr)\\
&= d\gcd\Bigl(a+b,\gcd(a,b)\Bigr)\\
&= d\gcd(a,b)\\
&= \gcd(a,b)\gcd(a,b).
\end{align*}
(Second line uses the fact that $a(a+b)$ and $b(a+b)$ are both multiples of $d(a+b)$).
Now divide through by $\gcd(a,b)$ to get the desired result.
A: Perhaps overkill, but if you accept the 'distribution law' $(x,[y,z])=[(x,y),(x,z)]$ stated at Wikipedia, then it is easy:
$(a+b,[a,b])=[(a+b,a),(a+b,b)]=[(b,a),(a,b)]=(a,b)$
where in the second equality I used the easy fact $(x,y)=(x,y \mod x)$.
A: Start by writing $a=d a'$, $b=d b'$, where $d=(a,b)$.
A: $\newcommand{\lcm}{\:\text{lcm}}$Here is an 'divisor-level' proof which basically mirrors Gone's first proof.  We can use the following definitions: $\;\gcd(a,b)\;$ and $\;\lcm(a,b)\;$ are the non-negative numbers such that, for all $\;d\;$,
\begin{array} \\
d|\gcd(a,b) & \equiv & d|a \land d|b \\
d|\lcm(a,b) & \equiv & d|a \lor d|b \\
\end{array}
together with 'divisor extentionality', i.e., $\;s = t \;\equiv\; \langle \forall d :: d|s \equiv d|t \rangle\;$ for non-negative numbers $\;s,t\;$.
We start with the most complex side of this equation, expand the above definitions, and try to simplify: for all $\;d\;$,
\begin{align}
& d|\gcd(a+b, \lcm(a,b)) \\
= & \;\;\;\;\;\text{"expand the definitions of $\;\gcd\;$ and $\;\lcm\;$"} \\
& d|(a+b) \;\land\; (d|a \lor d|b)) \\
= & \;\;\;\;\;\text{"distribute $\;\land\;$ over $\;\lor\;$"} \\
& (d|(a+b) \land d|a) \;\lor\; (d|(a+b) \land d|b) \\
= & \;\;\;\;\;\text{"on left hand side, use $\;d|a\;$ to simplify $\;d|(a+b)\;$; similar for right hand side"} \\
& (d|b \land d|a) \;\lor\; (d|a \land d|b) \\
= & \;\;\;\;\;\text{"logic: simplify; reintroduce definition of $\;\gcd\;$"} \\
& d|\gcd(a,b) \\
\end{align}
which by divisor extensionality proves $\;\gcd(a+b, \lcm(a,b)) = \gcd(a,b)\;$.
