Results 1 to 15 of 15

Math Help - hcf's and lcm's

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    hcf's and lcm's

    Let q_1=\frac{m_1}{n_1} and q_2= \frac{m_2}{n_2} be positive rational numbers. We define the lowest common multiple of q_1 and q_2, lcm (q_1,q_2), to be the smallest positive rational number q such that q=Mq_1=Nq_2 for some positive integers M and N.
    After that prelude, the question is this:

    Find a formula for lcm (q_1,q_2). Your answer can include expressions of the form lcm(m,n) and hcf(m,n) where m and n are integers.
    I know that hcf(m,n)( lcm (m,n))=mn but I have no idea where to go from here.

    Can someone point me in the right direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    LCM

    Hello Showcase_22

    If we assume that q_1=\frac{m_1}{n_1} and q_2=\frac{m_2}{n_2} are expressed in their lowest terms, then isn't the answer simply

    lcm(q_1, q_2) = lcm(m_1,m_2)?

    Or is there something smaller than that?

    Of course, if q_1 and q_2 are not in their lowest terms, then we can divide top-and-bottom by their hcf's to make them so, in which case the answer will be

    lcm \left(\frac{m_1}{hcf(m_1,n_1)}, \frac{m_2}{hcf(m_2,n_2)} \right)

    Or am I over-simplifying it?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    then isn't the answer simply

    lcm(q_1, q_2) = lcm(m_1,m_2)?
    Why ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Let's test it out:

    Find lcm(\frac{1}{7},\frac{2}{9})
    q=M\frac{1}{7}=N\frac{2}{9}

    q=M\frac{9}{63}=N \frac{14}{63}

    q=\frac{9(14)}{63}=\frac{9(14)}{63}=\frac{126}{63}  =2

    where M=14 and N=9.

    lcm(\frac{1}{7},\frac{2}{9})=lcm(1,2)=2

    So yes, <br />
lcm(q_1, q_2) = lcm(m_1,m_2)<br />
does work in this case.

    However, the next question is:

    Find lcm(\frac{3}{4}, \frac{5}{6})
    When this is substituted into your second formula you end up with exactly the same expression again.

    Maybe the expression is lcm(q_1,q_1)=lcm(m_1(lcm(n_1,n_2),m_2 lcm(n_1,n_2))?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2007
    Posts
    144
    Hello,

    You have hcf(q_1~,~q_2)\cdot lcm(q_1~,~q_2)=q_1\cdot q_2

    so; lcm(q_1~,~q_2)=\frac{q_1\cdot q_2}{hcf(q_1~,~q_2)}

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I know you can rearrange it like that, but that just turns the problem into finding an expression for the highest common factor of two rational numbers.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2007
    Posts
    144
    Quote Originally Posted by Showcase_22 View Post
    I know you can rearrange it like that, but that just turns the problem into finding an expression for the highest common factor of two rational numbers.
    I don't quite understand. The question only asks to find a formula, which can include hcf(m~,~n) where m , n are integers.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    LCM

    Hello everyone -

    I don't quite see what the problem is with my solution and the example
    Find lcm \left(\frac{3}{4},\frac{5}{6} \right)
    These two fractions are in their lowest terms, so, according to my original post, the answer should be lcm(3, 5) = 15. Is there anything smaller than this?

    In reply to Moo's question Why? It's something like this:

    Suppose first that q_1 = \frac{m_1}{n_1} and q_2 = \frac{m_2}{n_2} and that each fraction is in its lowest terms. In other words m_1 and n_1 are co-prime, and m_2 and n_2 are co-prime.

    Then:

    Lemma: If K is the smallest positive integer for which Kq_1 is an integer, then K = n_1 and therefore Kq_1 = m_1.

    Proof: Let K be the smallest positive integer for which Kq_1 is an integer.

    Then Kq_1 = \frac{Km_1}{n_1}

    Now n_1 and m_1 are co-prime \implies n_1 divides K \implies \exists n \in \mathbb{N}, n_1 \times n = K

    \implies n_1 = \frac{K}{n}

    \implies Kq_1 = \frac{Km_1n}{K} = m_1n

    \implies \frac{K}{n}q_1 = m_1 \in \mathbb{N}

    \implies n=1, since there is no smaller integer than K

    \implies K=n_1 \implies Kq_1 = m_1

    Obviously, in the same way, the smallest positive integer L for which Lq_2 \in \mathbb{N} is n_2, and Lq_2 = m_2.

    To find the lcm of q_1 and q_2, then, we need the smallest M, N for which q = Mq_1= Nq_2 and q \in \mathbb{N}.

    Now if q \in \mathbb{N} and q=Mq_1 then q = Pm_1, for some P \in \mathbb{N}, from the Lemma. Similarly q=Nq_2 \implies q=Qm_2, for some Q \in \mathbb{N}. So we now need to find the smallest P and Q for which Pm_1=Qm_2. Clearly these values are:

    P = \frac{lcm(m_1,m_2)}{m_1} and Q = \frac{lcm(m_1,m_2)}{m_2}

    and lcm(q_1,q_2) is therefore the same as the lcm(m_1,m_2).

    Finally, if q_1 and q_2 are not in their lowest terms, then, as I said in my original post, 'cancelling' each fraction by its respective hcf gives the result:

    lcm(q_1, q_2) = lcm \left(\frac{m_1}{hcf(m_1, n_1)},\frac{m_2}{hcf(m_2, n_2)} \right)

    Is that OK now?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Grandad,

    I have no intention to offend you, I just can't understand there may be a key to that...

    As an example, I believe the LCM of 3/4 and 5/6 is not 15 if we stick to the definition Showcase_22 gave in his first post.
    We indeed have :
    10 \times \frac 34=9 \times \frac 56=\frac{15}{2} ~ {\color{red}< 15}
    And this number, 15/2, satisfies all the conditions for being the LCM of 3/4 and 5/6. This is a contradiction to the fact that 15 is the LCM, isn't it ?

    In my humble opinion, the difference lies in the fact that the LCM of two rationals is a rational, not necessarily an integer.
    Last edited by Moo; January 4th 2009 at 12:05 AM. Reason: small edit
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Apologies

    So sorry - I should have read the question more carefully!

    Of course, I have been taking q as an integer.

    Apologies.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    LCM

    Hello everyone -

    Having now read the question properly(!), may I now suggest that my previous (wrong) answer has within it the germ of the solution. I haven't yet got a formal proof - perhaps someone else can confirm this by coming up with one - but it seems to me (intuitively? intelligent trial and error?) that the answer will be:

    lcm(q_1, q_2) = \frac{lcm(m_1,m_2)}{hcf(n_1, n_2)}

    provided, again, that q_1 and q_2 are given in their lowest terms. If not, the more general result (which is effectively obtained by 'cancelling' q_1 and q_2 until they are in their lowest terms) is:

    lcm(q_1, q_2) = \frac{lcm\left(\frac{m_1}{a},\frac{m_2}{b}\right)}  {hcf\left(\frac{n_1}{a}, \frac{n_2}{b}\right)}, where a=hcf(m_1,n_1) and b=hcf(m_2,n_2)

    Would anyone like to confirm this, or come up with a counter-argument?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I think it is important to notice (as Moo said) that the lcm can be rational.

    Q=M\frac{m_1}{n_1}=N\frac{n_2}{n_2}

    n_1n_2Q=Mm_1n_2=Nm_2n_1

    Taking Mm_1n_2=Nm_2n_1 we can deduce that M=lcm(m_2,n_1) and N=lcm(m_1,n_2). Therefore:

    n_1n_2Q=lcm(m_2,n_1) \cdot lcm(m_1,n_2)

    Q=\frac{lcm(m_2,n_1) \cdot lcm(m_1,n_2)}{n_1n_2}

    Check: find the lcm (\frac{1}{2},\frac{1}{4}) <-----This should be \frac{1}{2}
    \frac{m_1}{n_1}=\frac{1}{2} and \frac{m_2}{n_2}=\frac{1}{4}.

    Therefore: m_1=1, \ n_1=2, \ m_2=1, \ n_2=4.

    Q=\frac{lcm(1,2) \cdot lcm (1,2)}{4(2)}=\frac{2^2}{8}=\frac{1}{2} as required.

    This formula also appears to work!

    I can't actually figure out if this is the same as what you posted Grandad
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Aug 2007
    Posts
    144
    Quote Originally Posted by Showcase_22 View Post
    Q=\frac{lcm(m_2,n_1) \cdot lcm(m_1,n_2)}{n_1n_2}
    The formula only works if one of the numbers is a multiple of the other i.e. since 1/2 is a multiple of 1/4 then it works however we can show that it doesn't work where one number isn't a multiple of the other. For example,

    \mbox{lcm}\left(\frac{1}{3}~,~\frac{1}{2}\right)=1

    Yet,

    Let \frac{m_1}{n_1}=\frac{1}{3} and \frac{m_2}{n_2}=\frac{1}{2}

    then Q=\frac{\mbox{lcm}(1,3)\cdot \mbox{lcm}(1,2)}{3\cdot 6}=\frac{3\cdot 2}{3\cdot 6}=\frac{1}{3}\neq 1
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    LCM

    Hello showcase_22
    Taking we can deduce that
    I'm afraid I don't see how you can deduce that, and as Sean12345 has shown, the formula you end up with doesn't seem to work.

    Can I show you how I arrived at my (second!) conclusion, even though I haven't got a formal proof of the result?

    First I tried to get a feel for what was happening, by taking a few examples, trying to cover as many different cases as I could. In these examples, I'm assuming that the fractions are in their lowest terms. (If they're not, as I have said, just cancel by dividing the numerator and denominator by their hcf, and carry on from there.)

    Example 1
    q_1=\frac{3}{7}, q_2=\frac{4}{5}

    Here neither the numerators nor the denominators have any common factors (they are all co-prime). We need to find positive integers M and N such that:

    \frac{3}{7}M = \frac{4}{5}N (1)

    \implies M must be a multiple of 7, say 7m, and N is a multiple of 5, say 5n, in order to get rid of the denominators - since they don't have any common factor (other than 1, of course).

    Substituting these into (1) gives 3m = 4n. The lowest integer values that satisfy this are m=4 and n=3, giving M = 28, N= 15, and lcm(\frac{3}{7},\frac{4}{5}) = 12. Note in passing that lcm(3,4)=12.

    Example 2
    q_1 = \frac{3}{14}, q_2 = \frac{4}{35}

    Now I've kept the same numerators, but have made the denominators have a common factor 7. Look what happens:

    \frac{3}{14}M = \frac{4}{35}N

    If we try M = 14m and N = 35n we get

    3m = 4n

    again giving the lowest values m=4, n=3 and so M=56, N = 105

    This would again give an lcm of 12. This would have been my (wrong) original answer - wrong because I was assuming that the lcm, q, had to be an integer. But it doesn't - and there are smaller values of M and N that work now, which you can get by dividing by their hcf: 7. So, instead of M=14m and N=35n, divide by their highest common factor 7, and write

    M = 2m and N = 5n

    This gives \frac{3}{14}\times 2m = \frac{4}{35}\times 5n

    \implies \frac{3}{7}m = \frac{4}{7}n

    again giving m = 4 and n = 3, but this time M=8 and N=15, and so lcm(\frac{3}{14}, \frac{4}{35})= \frac{12}{7}. (Note that the answer is now lcm(3,4) divided by hcf(14, 35).)

    Do you see where I'm going with this?

    I suggest you try out a few examples of your own, varying the values of m_1, n_1, m_2 and n_2 one at a time, so that you cover all combinations:


    • hcf(m_1, m_2) = 1 and hcf(n_1, n_2)=1 (in other words the numerators are co-prime and so are the denominators)
    • hcf(m_1, m_2) = 1 and hcf(n_1, n_2)>1
    • hcf(m_1, m_2) > 1 and hcf(n_1, n_2)=1
    • hcf(m_1, m_2) > 1 and hcf(n_1, n_2)>1

    In all cases, make sure that your fractions are cancelled to their lowest terms. See what you get. I think you'll find that the formula is the one I gave in my second attempt!

    Let us know how you get on.

    Grandad

    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    LCM: Formal Proof

    Hello showcase_22

    Here's a complete proof of the formula. It centres around pairs of numbers that are co-prime, that is, numbers whose highest common factor is 1. Here we go:
    Let and be positive rational numbers. We define the lowest common multiple of and , lcm , to be the smallest positive rational number q such that for some positive integers M and N.
    Find a formula for . Your answer can include expressions of the form lcm(m,n) and hcf(m,n) where m and n are integers.
    We may assume that q_1 and q_2 are expressed in their lowest terms; i.e. m_1 and n_1 are co-prime and m_2 and n_2 are co-prime. (If not, they should be expressed in their lowest terms by 'cancelling'.) The formula then is:

    q = \frac{l}{h}

    where l = lcm(m_1, m_2) and h = hcf(n_1, n_2)

    Proof

    First we look at two lemmas which could be said to define lcm and hcf.

    (1) Lemma 1: If l = lcm(m_1,m_2) then for some integers p_1 and p_2, l=m_1p_1 = m_2p_2 if and only if p_1 and p_2 are co-prime.

    Proof of Lemma 1:

    (A) If l = m_1p_1 = m_2p_2 and p_1 and p_2 are not co-prime, then dividing through by their common factor will give a common multiple that is smaller than l. Contradiction.

    (B) If p_1 and p_2 are co-prime, and m_1p_1 = m_2p_2, then each product = l=lcm(m_1, m_2) because (i) each product is a common multiple, and (ii) if there are smaller integers, r_1 and r_2, say, for which m_1r_1 = m_2r_2, then \frac{p_1}{r_1} = \frac{p_2}{r_2} \Rightarrow p_1= \frac{p_2}{r_2}r_1 = kr_1 for some k>1. Similarly p_2=kr_2  \Rightarrow p_1 and p_2 have common factor k. Contradiction.

    In a similar way, we may prove

    (2) Lemma 2: If h = hcf(n_1, n_2), then for some integers p_3, p_4, n_1=hp_3 and n_2 = hp_4 if and only if integers p_3 and p_4 are co-prime.

    Proof of formula

    We need to find q such that M and N are the smallest integers where

    q = \frac{Mm_1}{n_1} = \frac{Nm_2}{n_2}

    Then:

    (3) M and N are co-prime, for if not, we may divide throughout by their common factor to find smaller integers.

    Using the notation in Lemma 2 we may re-write this as:

    q=\frac{Mm_1}{hp_3} = \frac{Nm_2}{hp_4}

    \Rightarrow \frac{Mm_1}{p_3}=\frac{Nm_2}{p_4} (4)

    \Rightarrow M = \frac{Nm_2p_3}{m_1p_4}

    Now n_1 and m_1 are co-prime \Rightarrow p_3 and m_1 are co-prime; and from Lemma 2, p_3 and p_4 are co-prime. So M is a multiple of p_3. So we may write:

    M = mp_3, for some integer m.

    Similarly N = np_4, for some integer n.

    So, from (4):

    mm_1 = nm_2

    And, from (3), m and n are co-prime, since M and N are co-prime.

    Thus, from Lemma 1, mm_1 = nm_2 = lcm(m_1, m_2) = l

    \Rightarrow m = \frac{l}{m_1}

    \Rightarrow M = \frac{lp_3}{m_1}

    \Rightarrow q =\frac{Mm_1}{n_1}= \frac{lp_3m_1}{m_1n_1}

    = \frac{lp_3}{hp_3}

    = \frac{l}{h}

    QED

    Grandad
    Last edited by Grandad; January 6th 2009 at 02:26 AM. Reason: Amendment to proof of Lemma 1
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum