15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Joyce May 13 '12 at 20:16
  • $\begingroup$ @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 $\endgroup$ – mrs May 13 '12 at 20:21
16
$\begingroup$

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$

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

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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