# Proof via Group Theory : $\mathrm{lcm}(a,b) \cdot \gcd(a,b) = |ab|$

Recently, I was informed that we can verify the famous formula about $\mathrm{lcm}(a,b)$ and $\gcd(a,b)$ which is $$\mathrm{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)}$$ via group theory.

The least common multiple of two integers $a$ and $b$, usually denoted by $\mathrm{lcm}(a,b)$, is the smallest positive integer that is a multiple of both $a$ and $b$ and the greatest common divisor ($\gcd$), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

I do not know if we can prove this equation by using the groups or not, but if we can I am eager to know the way someone face it. Thanks.

• If you use the fundamental theorem of arithmetic (every integer can be factored uniquely into a product of primes), then your identity reduces down to the fact that $\max(a,b) + \min(a,b) = a + b$ for any two numbers $a, b$. – Michael Joyce May 13 '12 at 20:16
• @MichaelJoyce: You noted here a great hint Michael, but I am curious to examine this identity with group theory. Honestly, I was strongly told that we can prove it. Thanks – mrs May 13 '12 at 20:21

Lemma. Let $G$ be a group, written multiplicatively, and let $H$ and $K$ be two subgroups. If $HK = \{hk\mid h\in H, k\in K\}$, then $$|HK||H\cap K| = |H||K|$$in the sense of cardinalities.

Proof. Consider the map $H\times K\to HK$ given by $(h,k)\mapsto hk$. I claim that the map is exactly $|H\cap K|$ to $1$. Indeed, if $hk=h'k'$, then $h'^{-1}h = k'k^{-1}\in H\cap K$, so there exists $u\in H\cap K$, namely $u=h'^{-1}h$ such that $h=h'u$ and $k=u^{-1}k'$. Thus, $(h,k) = (h'u,u^{-1}k')$ maps to the same thing as $(h',k')$. Conversely, given $v\in H\cap K$, we have that $(h'v,v^{-1}k')\in H\times K$ maps to the same thing as $(h',k')$.

Thus, each element of $HK$ corresponds to precisely $|H\cap K|$ elements of $H\times K$. Thus, $|HK||H\cap K| = |H\times K| = |H||K|$, as claimed. $\Box$

Let $a$ and $b$ be integers, and consider $\mathbb{Z}/\langle ab\rangle$. This is a group with $|ab|$ elements. This group contains subgroups generated by $\gcd(a,b)$, by $a$, by $b$, and by $\mathrm{lcm}(a,b)$. $\gcd(a,b)$ generates the largest subgroup containing both $a$ and $b$; i.e., $\langle \gcd(a,b)\rangle = \langle a\rangle + \langle b\rangle$; while $\mathrm{lcm}(a,b)$ generates the smallest subgroup contained in both $\langle a\rangle$ and $\langle b\rangle$, i.e., $\langle \mathrm{lcm}(a,b)\rangle = \langle a\rangle\cap\langle b\rangle$. By the Lemma (with addition, since we are working in an additive group), we have: $$|\langle a\rangle+\langle b\rangle| |\langle a\rangle\cap\langle b\rangle| = |\langle a\rangle||\langle b\rangle|$$ Now, the subgroup generated by $\gcd(a,b)$ has $\frac{|ab|}{\gcd(a,b)}$ elements; the subgroup generated by $\mathrm{lcm}(a,b)$ has $\frac{|ab|}{\mathrm{lcm}(a,b)}$ elements; that generated by $a$ has $\frac{|ab|}{|a|}$ elements, that generated by $b$ has $\frac{|ab|}{|b|}$ elements. Plugging all of that in it becomes $$\gcd(a,b)\mathrm{lcm}(a,b) = |a||b|$$ which yields the desired equality. $\Box$

• Thanks Prof. Arturo for your complete help. Thanks lhf for the first steps of this problem given to me. – mrs May 13 '12 at 20:43

Consider the canonical map $\mathbb Z \to \mathbb Z/(a) \times \mathbb Z/(b)$ given by $x\mapsto (x \bmod a, x \bmod b)$.

What is the kernel? What is the image?

• Is its kernel equal to $(d)$ which $d=(a,b)$? – mrs May 13 '12 at 20:30
• @BabakSorouh, no: $x$ is in the kernel iff $x$ is multiple of both $a$ and $b$. – lhf May 13 '12 at 20:31
• Sorry. you meant $d=ab$. Do you want to use the first theorem about homomorphism here? – mrs May 13 '12 at 20:35
• Use $m=[a,b]$ and $d=(a,b)$ to avoid confusion. Yes,the first homomorphism theorem will be useful. – lhf May 13 '12 at 20:36