# $\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])$.

-
This looks like homework. What have you tried? – Ross Millikan Feb 11 '11 at 15:43
@kira: If it is homework, please use the [homework] tag. For these kinds of problems, please use the [elementary-number-theory] tag, not [number-theory]. And, please, if you have a question, then phrase it like a question, not like an order. – Arturo Magidin Feb 11 '11 at 16:23
I am confused. You say: in the following, "(,)=gcd". But then in the following you write "gcd(a,b)". I suspect you actually wanted to write "(a,b)" in the following? So (a,b)=(a+b,[a,b])? – wildildildlife Feb 11 '11 at 16:26
@Arturo: I am new here! Sorry! – kira Feb 11 '11 at 16:44
@wildil..: Right! I need (a,b)=(a+b,[a,b]). – kira Feb 11 '11 at 16:45

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]\ =\ ab\ \$ and basic gcd laws:

$\rm\quad (a,b)\ (a+b, [a,b])\ =\ (aa+ab,\ ab+bb,\ ab)\ =\ (aa,\:bb,\:ab)\ =\ (a,b)^2\quad$ QED

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\ \ \ (a,\:b)^2 \subset (a+b,\:ab) \subset (a,\:b)\ \$ since e.g. $\rm\ \ a^2 = a\:(a+b)-ab\in (a+b,\:ab)$

Thus $\rm\ 1\in (a+b,\ ab)\ \Rightarrow\ 1\in (a,\:b)\:.\:$ Conversely $\rm\ 1 \in (a,\:b)\ \Rightarrow\ 1 \in (a,\:b)^2 \subset (a+b,\:ab)\quad$ QED

-

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.

-
Bill must be feeling at least some pride; after so many years of following up in sci.math with "SIMPLER...", I've finally started looking for arguments along these lines, even if they aren't the best one available just yet. – Arturo Magidin Feb 11 '11 at 22:04
Thanks, you're too kind. Although I haven't checked all the details, I think the above derivation is - at the core - closely related to the one in my post employing the GCD*LCM law. It should prove illuminating to compare the two. – Gone Feb 12 '11 at 2:47
@Bill: If I'm not mistaken, it's the one you labeled "for variety"; at least, that's the identity I was trying to establish when this computation worked. – Arturo Magidin Feb 12 '11 at 5:36

Start by writing $a=d a'$, $b=d b'$, where $d=(a,b)$.

-
 $l = da'b'$ and $(a',b')=1$. – lhf Feb 11 '11 at 16:55 Ok. Let d=(a,b), and l=[a,b]. Then d=(a+b,l). But a|l and b|l which means that l=am=bn for some positive integers m,n. Know also that a=da' and b=db' for some positive integers a', and b'. l=da'b' and (a',b')=1. Also ab=ld. – kira Feb 11 '11 at 17:03 Let (a+b,l)=gcd(a+b,bn). Then gcd(a+b,bn)|a+b and gcd(a+b,bn)|bn by the definition of gcd. But gcd(a+b,bn)|(a+b)-b by the linear combination property. So, gcd(a+b,bn)|a. Similarly gcd(a+b,bn)|b.So, gcd(a+b,bn)|(a,b) and vice versa. So, (a,b)=(a+b,[a,b]). – kira Feb 11 '11 at 17:20 Can anyone evaluate my writing of proof? Thanks! – kira Feb 11 '11 at 17:25 @kira: Next time, write it as an addendum to your question; that way, the activity is reflected in the main page. I'll read it shortly and comment. – Arturo Magidin Feb 11 '11 at 21:08
show 1 more comment

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

-