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.

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.

share|improve this question
    
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 –  B. S. May 13 '12 at 20:21
add comment

2 Answers

up vote 12 down vote accepted

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$

share|improve this answer
    
Thanks Prof. Arturo for your complete help. Thanks lhf for the first steps of this problem given to me. –  B. S. May 13 '12 at 20:43
add comment

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?

share|improve this answer
    
Is its kernel equal to $(d)$ which $d=(a,b)$? –  B. S. 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? –  B. S. 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
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.