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.

I'm looking for an understandable proof of this theorem, and also a complex one involving beautiful math techniques such as analytic number theory, or something else. I hope you can help me on that. Thank you very much

share|improve this question
3  
This isn't really a deep enough identity to have a complicated proof. –  Qiaochu Yuan Apr 3 '13 at 6:47
5  
If you think of numbers as (multi)sets of prime numbers, it's really very obvious. GCD is the (multiset) intersection of $a$ and $b$, LCM is their symmetric difference (xor), and multiplication gives multiset union. Or in simpler terms: GCD is where they overlap, LCM is where they don't, and the $\times$ combines the two. Obviously that'll just give you the union, ie $ab$. This wouldn't really be a proof unless you defined the multi-set analogy rigorously, though (which would be easy but boring). –  Jack M Apr 3 '13 at 6:52
    
@JackM: What do you mean by "symmetric difference (xor) of multisets", or "LCM is where they don't"?? –  Marc van Leeuwen Apr 3 '13 at 8:24
1  
@MarcvanLeeuwen Sorry, I misspoke. LCM is not the symmetric difference of multisets. LCM is actually the smallest multiset containing both $a$ and $b$, which in particular makes it the multiset union of $a$ and $b$ minus the multiset intersection of $a$ and $b$. With regular sets that would indeed be the XOR, but with multisets it's a bit (not much) more complicated. The OP's proposition still follows trivially, however. –  Jack M Apr 3 '13 at 12:46
    
@JackM: The smallest multiset containing both $a$ and $b$ is what is usually called the multiset union of $a$ and $b$, which differs from the multiset sum by their multiset intersection. And for regular sets you get the ordinary union, corresponding to (inclusive) OR. –  Marc van Leeuwen Apr 3 '13 at 12:52

6 Answers 6

up vote 9 down vote accepted

Let $\gcd(a,b)=d$. Then for some $a_0,b_0$ such that $a_0$ and $b_0$ are relatively prime, we have $a=da_0$ and $b=d b_0$. If we can show that the lcm of $a$ and $b$ is $da_0b_0$, we will be finished.

Certainly $da_0b_0$ is a common multiple of $a$ and $b$. We must show that it is the least common multiple.

Let $m$ be a common multiple of $a$ and $b$. We will show that $da_0b_0$ divides $m$.

Since $m$ is a multiple of $a$, we have $m=ka=ka_0d$ for some $k$. But $b$ divides $m$, so $db_0$ divides $ka_0d$, and therefore $b_0$ divides $ka_0$. Since $a_0$ and $b_0$ are relatively prime, it follows that $b_0$ divides $k$, and we are finished.

share|improve this answer
    
+1. But in the end you used a version of Euclid's lemma, which can be avoided. –  Marc van Leeuwen Apr 3 '13 at 8:47

The following is more general than for the integers, and therefore simpler (but longer than a proof using unique factorisation without proving it; here we start from scrap).

Let $R$ be an integral domain, where $d=\gcd(a,b)$ is defined to mean that $d\mid a,b$ and $d'\mid a,b\implies d'\mid d$ for all $d'\in R$, while $\def\lcm{\operatorname{lcm}}m=\lcm(a,b)$ is defined to mean that $a,b\mid m$ and $a,b\mid m'\implies m\mid m'$ for all $m'\in R$ (in both cases it is not implied that $\gcd(a,b)$ or $\lcm(a,b)$ always exist, and if they do they are only unique up to multiplication by invertible elements).

Lemma. Let $r\in R\setminus\{0\}$, and put $D_r=\{\, d\in R: d\mid r\,\}$, the set of divisors of $r$. Then $f_r:d\mapsto r/d$ defines an involution of $D_r$ which is an anti-isomorphism for the divisibility relation: for $a,b\in D_r$ one has $a\mid b\iff f(b)\mid f(a)$.

Proof. Since by definition $d f(d)=r$ for all $d\in D_r$ one has $f(d)\in D_r$ and $f(f(d))=d$. Suppose $a,b\in D_r$ satisfy $a\mid b$, so there exists $c\in R$ with $ac=b$, then $r=bf(b)=acf(b)$ so $f(a)=cf(b)$ and $f(b)\mid f(a)$. Conversly if $f(b)\mid f(a)$ applying this result gives $f(f(a))\mid f(f(b))$ which simplifies to $a\mid b$. QED

Proposition. If $ab\neq0$ and $m=\lcm(a,b)$ exists, then $ab/m=\gcd(a,b)$.

Proof. One has $a,b\mid ab$ so $m\mid ab$ by definition of the $\lcm$; therefore $a,b,m\in D_{ab}$. One has $f_{ab}(a)=b$ and $f_{ab}(b)=a$, and since $a,b\mid m$ one has $f_{ab}(m)\mid b,a$ by the lemma. Also if $d'\in R$ satisfies $d'\mid a,b$ then $d\in D_{ab}$ so $b,a\mid f_{ab}(d')$ by the lemma, whence $m\mid f_{ab}(d')$ by definition of the $\lcm$, and once again by the lemma $d'\mid f_{ab}(m)$. Thus $$ab/m=f_{ab}(m)=\gcd(a,b). \qquad\text{QED}$$

Concluding $\gcd(a,b)\times \lcm(a,b)=ab$ needs the precaution that it only holds if $\lcm(a,b)$ exists, and then the left hand side is defined up to invertible factors only, so the equality should be interpreted in this sense. For the case $ab=0$ not covered by the proposition one has $0=\lcm(a,b)$ and $\{a,b\}=\{0,\gcd(a,b)\}$, so the equality holds without any difficulty.

Note that the existence of $\gcd(a,b)$ does not imply the existence of $\lcm(a,b)$ in general.

share|improve this answer
    
Readers can find another involution-based proof in this answer. –  Bill Dubuque Feb 26 at 18:44

Transcribed from my ASCII page:

First notice that $$ \dfrac{ab}{\gcd(a,b)} = a\dfrac{b}{\gcd(a,b)} = b\dfrac{a}{\gcd(a,b)} $$ is a common multiple of $a$ and $b$. By the minimality of the $\operatorname{lcm}$, $$ \frac{ab}{\gcd(a,b)}\ge\operatorname{lcm}(a,b)\Longrightarrow ab\ge\operatorname{lcm}(a,b)\gcd(a,b)\tag{1} $$ By division, we can write $$ ab = q\operatorname{lcm}(a,b) + r\quad\text{where}\quad0 \le r \lt \operatorname{lcm}(a,b) $$ Because $ab$ and $\operatorname{lcm}(a,b)$ are common multiples of $a$ and $b$, so is $r$. By the minimality of the $\operatorname{lcm}$, $r = 0$. Therefore, $\operatorname{lcm}(a,b)$ divides $ab$. Notice that $$ \frac{ab}{\operatorname{lcm}(a,b)} = \frac{a}{\operatorname{lcm}(a,b)/b} = \frac{b}{\operatorname{lcm}(a,b)/a} $$ is a common divisor of $a$ and $b$. By the maximality of the $\gcd$, $$ \frac{ab}{\operatorname{lcm}(a,b)} \le \gcd(a,b)\Longrightarrow ab\le\operatorname{lcm}(a,b)\gcd(a,b)\tag{2} $$ Combining $(1)$ and $(2)$, we get $$ ab = \operatorname{lcm}(a,b)\gcd(a,b) $$

share|improve this answer
    
very nice and elementary –  Jonathan Apr 3 '13 at 14:17
1  
@Jonathan: Elementary!? I don't see an elementary but nice formal approach. here :-) –  Babak S. Apr 3 '13 at 17:37
    
I'm not sure what you mean, but I didn't mean "elementary" in any pejorative sense -- just working with simple tools. –  Jonathan Apr 3 '13 at 17:42
1  
@Jonathan: I took it as a compliment :-) –  robjohn Apr 3 '13 at 18:32

Let's prime factorize a and b.Let $a=p_1^{x_1}p_2^{x_2}\cdots\cdot q$ and $b=p_1^{y_1}p_2^{y_2}\cdots r$ where $(p_i,r)=1$ , $(p_i,q)=1$,$(p_i,p_j)=1(r,q)=1$ Then

GCD$(a,b)=p_1^{\min(x_1,y_1)}p_2^{\min (x_2,y_2)} \cdots$

LCM$(a,b)= qrp_1^{max(x_1,y_1)}p_2^{\max(x_2,y_2)}\cdots$

LCM$(a,b)$GCD$(a,b)=ab$

share|improve this answer

The following simple proof works in any integral domain.

Theorem $\rm\quad gcd(a,b)\, =\, ab/lcm(a,b)\ \ $ if $\ \ \rm lcm(a,b) \;$ exists, and $\rm\ ab\ne 0$

Proof $\rm\quad d\mid a,b\!\iff\! a,b\mid ab/d \!\iff\! lcm(a,b)\mid ab/d \iff d\mid ab/lcm(a,b)$

share|improve this answer
    
The middle equivalence is true, but $a,b\mid c\Rightarrow\mathrm{lcm}(a,b)\mid c$ almost feels like we're assuming something we are trying to show. It may be that things are so basic at this level, that I am not sure what we can assume. –  robjohn Apr 3 '13 at 20:35
    
@robjohn It is not circular. The hypothesis that $\rm\ lcm(a,b)\ $ exists means, by *definition*, that $\rm\ a,b\mid x\iff lcm(a,b)\mid x.\:$ Dually, $\rm\ x\mid a,b \iff x\mid gcd(a,b),\:$ if said gcd exists. These are the universal definitions of lcm,gcd used in general domains, where least/greatest means wrt divisibility. They're equivalent to the well-known definitions in Euclidean domains, where least/greatest means wrt Euclidean value ("size"), e.g. $\rm\:|x|\:$ in $\rm\:\Bbb Z,\:$ and $\rm\:deg(f(x))\:$ in $\rm\:F[x].$ –  Math Gems Apr 3 '13 at 20:59
    
My impression was that $\mathrm{lcm}(a,b)$ is the least positive number that is a multiple of both $a$ and $b$. That it divides all other common multiples of $a$ and $b$ is not immediately obvious. This is why I felt it necessary to prove that $\mathrm{lcm}(a,b)\mid ab$ in my answer. –  robjohn Apr 3 '13 at 21:13
    
@robjohn The division algorithm yields a one-line proof that in $\rm\,\Bbb Z\,$ a common multiple is least in value iff it is divisibly least (i.e. divides all common multiples). Similarly in other Euclidean domains, as I said above. –  Math Gems Apr 3 '13 at 21:37
    
Yes, that is essentially the proof that I used. However, I assume that the person asking a basic question would be dealing in $\mathbb{Z}$, and have little familiarity with other Euclidean domains. This is the basis of my earlier discomfort. In any case, I see where you are coming from. (+1) –  robjohn Apr 3 '13 at 21:47

I think this is a simple one:

By definition, a least common multiple of a pair of integers $a$ and $b$ is an integer $m$ such that $a|m$, $b|m$, and $m$ divides every common multiple of $a$ and $b$.

Just look that if $c$ is a common multiple of $a$ and $b$, we have that $c=ax=by$ for some integers $x$ and $y$.

Then $\frac{a}{(a,b)}x=\frac{b}{(a,b)}y$, and because $\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1$, we have that $\frac{a}{(a,b)}$ divides $y$.

So $y=\frac{a}{(a,b)}n$ for some integer $n$ and $c=\frac{ba}{(a,b)}n$. This shows that every time you have a common multiple of $a$ and $b$ it can be divisible by $\frac{ba}{(a,b)}$, then $[a,b]=\frac{ba}{(a,b)}$.

share|improve this answer

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.