Easiest and most complex proof of $\gcd (a,b) \times \operatorname{lcm} (a,b) =ab.$

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

• This isn't really a deep enough identity to have a complicated proof. Apr 3, 2013 at 6:47
• 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). Apr 3, 2013 at 6:52
• @JackM: What do you mean by "symmetric difference (xor) of multisets", or "LCM is where they don't"?? Apr 3, 2013 at 8:24
• @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. Apr 3, 2013 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. Apr 3, 2013 at 12:52

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.

• @DonLarynx: They meaning $a_0$ and $b_0$? If they are not, then $a$ and $b$ have a common divisor greater than $d$. Jan 26, 2015 at 17:20
• Thank you for your reply André , however it is not clear to me how that is true. If $d = gcd(a, b)$ then we have $da_0 = a$ and $db_0 = b$. Then, assuming $gcd(a_0, b_0) \neq 1$ and $b_0 \geq a_0$, we have $\exists k \in\Bbb{Z} : b_0 = ka_0$ and thus $da_0 = a, dka_0 = b$. But all that this tells me is that $d$ and $a_0$ are divisors of $a, b$. That means that $d*a_0$ would be the gcd instead of $d$. So is that interpretation correct? Jan 26, 2015 at 17:36
• @DonLarynx: Details depend on how one defines gcd. I am taking the school definition, biggest common divisor, though we can adjust the proof if we use the "divides every common divisor" definition. Suppose that $a_0$ and $b_0$ are not relatively prime. Then some $w\gt 1$ divides both of them. Then $dw$ divides both $a$ and $b$, contradicting the fact that $d$ is the gcd of $a$ and $b$. Jan 26, 2015 at 17:46
• Why does $db_0 | dka_0$ imply that $b_0 | ka_0$? Feb 4, 2015 at 20:51
• @YaseenMollik $m=k a_0 d$ and if you divide that by $a_0b_0d$ then $a_0,d$ cancel so if $b_0$ divides $k$ then the division gives an integer. Jun 29, 2020 at 13:56

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

• very nice and elementary Apr 3, 2013 at 14:17
• @Jonathan: Elementary!? I don't see an elementary but nice formal approach. here :-) Apr 3, 2013 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. Apr 3, 2013 at 17:42
• @Jonathan: I took it as a compliment :-)
– robjohn
Apr 3, 2013 at 18:32
• @Junglemath: I had tried to show that in the passage above, starting at "By division, we can write" and ending at "Therefore, $\operatorname{lcm}(a,b)$ divides $ab$."
– robjohn
Nov 20, 2019 at 5:43

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; as a consequence in this setting the equality $$\gcd(a,b)\times\lcm(a,b)=ab$$ can only be asserted up to such multiplication, or for properly chosen values on the left hand side).

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.

• Readers can find another involution-based proof in this answer. Feb 26, 2014 at 18:44
• Dear Marc! Let me ask you the following question: If $ab=0$ then at least one of them is zero since we are in Integral Domain, i.e. $a=0$ or $b=0$. How it follows that $\text{lcm}(a,b)=0$? Suppose that $a=0$ then $\text{lcm}(a,b)=\text{lcm}(0,b)$ but the last term is meaningless.
– ZFR
Jun 16, 2018 at 14:25
• @ZFR The only multiple of $0$ is $0$ itself, which is also a multiple of any other element of $R$. So even without pondering on the meaning of "least" here, it stands to reason that $\operatorname{lcm}(0,b)=0$ for any $b$, and indeed that is how it is defined whenever one wants $\operatorname{lcm}$ to be defined for all elements (and for completeness, $\gcd(0,b)=b$ for any $b$). And by "the equation" I refer to the one of the title of the OP question. Oct 1, 2020 at 12:07

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$$'s are distinct primes and GCD$$(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$$

Then since $$\min(x, y) + \max(x, y) = x+y$$, we have LCM$$(a,b)$$GCD$$(a,b)=ab$$

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

The following simple duality-based 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\!\color{#c00}\iff\! a,b\mid ab/d \!\iff\! lcm(a,b)\mid ab/d \color{#c00}\iff d\mid ab/lcm(a,b)$$

Remark $$\$$ The red equivalences are $$\rm\:x\mid y\color{#c00}\iff y'\mid x'\:$$ for $$\rm\ x'\! = ab/x\$$ being reflection on the divisors of $$\rm\:ab,\:$$ highlighting the $$\rm\ gcd = lcm' \$$ duality, namely

$$\rm gcd(a,b)\, =\, \frac{ab}{lcm(b,a)}\, =\, lcm(a',b)'\qquad\quad$$

See here for a proof emphasizing this reflection (involution) and the innate duality.

• 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, 2013 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].$ Apr 3, 2013 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, 2013 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. Apr 3, 2013 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, 2013 at 21:47

I don't know that you are familiar to the Group theory, but if you consider groups $\mathbb Z_a$ and $\mathbb Z_b$ then the following homomorphism can do what you are looking for. I mean: $$\phi: \mathbb Z\to\mathbb Z_a\times\mathbb Z_b,~~~~n\mapsto(n|_{\text{mod}~a},n|_{\text{mod}~b})$$

• I can see that the LCM generates the kernel of this homomorphism, but would you please explain where the GCD comes in? It should be the index of the image in the codomain, but is this so obvious? Apr 3, 2013 at 8:22
• @MarcvanLeeuwen: Honestly, at the first view, No. You are right. In fact the OP should use the first theorem of homomorphism and find the kernel and the image of the map. However, the OP preferred the answer via number theory approach. Apr 3, 2013 at 8:30

Brute Force Approach
We can write $$a$$ and $$b$$ in the following manner: $$a=d x_0,\;b=d y_0$$ $$m=a p_0=b q_0$$ Here $$d=gcd(a,b)$$ and $$m=lcm(a,b)$$. And both $$\{x_0,y_0\}$$ and $$\{p_0,q_0\}$$ are sets of co-prime numbers.

By multiplication, we can write: $$ab=d^2x_0y_0$$ $$ab\cdot p_0 q_0=m^2$$ Multiplying both equations: $$(ab)^2\cdot p_0q_0=(md)^2 \cdot x_0y_0$$ Now we only need to prove that $$p_0q_0=x_0y_0$$, in fact we can prove that $$x_0=q_0$$ and $$y_0=p_0$$.

Using the first two equations: $$\frac{a}{b}=\frac{x_0}{y_0}=\frac{q_0}{p_0}$$ Because $$\{x_0,y_0\}$$ and $$\{p_0,q_0\}$$ are sets of co-prime numbers, both $$\frac{x_0}{y_0}$$ and $$\frac{q_0}{p_0}$$ are the simplest or irreducible fractions of $$\frac{a}{b}$$. Hence both the numerators and denominators are equal i.e. $$x_0=q_0$$ and $$y_0=p_0$$.
$$\require{cancel} (ab)^2\cdot \cancel{p_0q_0}=(md)^2 \cdot \cancel{x_0y_0}$$ $$(ab)^2=(md)^2 \Rightarrow ab=md$$

Easy proof:

$$[p,q] = p*q, \space if \space (p, q) = 1$$ [p, q] = lcm(p, q) and (p, q)=gcd(p, q). This can be proved using only simple property of relatively prime numbers.

Another fact: $$[mp, mq] = m[p, q] \space if \space m\in N$$ Since common multiple is all about dividable relation, multiply everything by m won't change that.
let $$(p, q) = d, so \space (p/d,q/d)=1$$ $$(p,q)[p,q] = d*d*[p/d,q/d]=d*d*\frac{p}{d}*\frac{q}{d}=pq$$

Easy proof by set theory: (I'm a beginner and thought of this, please correct if me if I'm wrong)

Let $$a=xy, b=xz$$.

So $$a = \{x,y\}$$ and $$b = \{x, y\}$$,

where $$x$$ is the product of the common prime factors of $$a, b$$ which is $$\gcd(a,b)$$ and the product $$xyz$$ produces $$\text{lcm}(a,b)$$

By Set Theory,

$$P(a \cup b) \cdot P(a \cap b) = P(a) \cdot P(b)$$.

$$xyz \cdot x = xy \cdot xz$$

lcm(a,b) * gcd(a,b) = ab

• Please note that "set theory" is a whole different subject that has nothing to do with this Nov 26, 2016 at 13:42