Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
This looks like homework. What have you tried? –  Ross Millikan Feb 11 '11 at 15:43
1  
@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
2  
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
show 2 more comments

5 Answers 5

up vote 5 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|improve this answer
add comment

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|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
2  
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
add comment

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

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

share|improve this answer
add comment

$\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|improve this answer
add comment

Your Answer

 
discard

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.