Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show that if $a$, $b$ are positive integers, then we have: $\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$.

share|cite|improve this question
up vote 6 down vote accepted

Below are a few proofs. First, here's a couple from my sci.math post on 2001/11/10 enter image description here
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

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Bill Dubuque 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)$.

share|cite|improve this answer
$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

Perhaps overkill, but if you accept the 'distribution law' $(x,[y,z])=[(x,y),(x,z)]$ stated at Wikipedia, then it is easy:


where in the second equality I used the easy fact $(x,y)=(x,y \mod x)$.

share|cite|improve this answer

$\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|a \equiv d|b \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)\;$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.