Results 1 to 15 of 15

Thread: 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 $\displaystyle q_1=\frac{m_1}{n_1}$ and $\displaystyle q_2= \frac{m_2}{n_2}$ be positive rational numbers. We define the lowest common multiple of $\displaystyle q_1$ and $\displaystyle q_2$, lcm $\displaystyle (q_1,q_2)$, to be the smallest positive rational number q such that $\displaystyle q=Mq_1=Nq_2$ for some positive integers M and N.
    After that prelude, the question is this:

    Find a formula for $\displaystyle 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 $\displaystyle 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
    Thanks
    1

    LCM

    Hello Showcase_22

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

    $\displaystyle lcm(q_1, q_2) = lcm(m_1,m_2)$?

    Or is there something smaller than that?

    Of course, if $\displaystyle q_1$ and $\displaystyle 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

    $\displaystyle 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

    $\displaystyle 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 $\displaystyle lcm(\frac{1}{7},\frac{2}{9})$
    $\displaystyle q=M\frac{1}{7}=N\frac{2}{9}$

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

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

    where $\displaystyle M=14$ and $\displaystyle N=9$.

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

    So yes, $\displaystyle
    lcm(q_1, q_2) = lcm(m_1,m_2)
    $ does work in this case.

    However, the next question is:

    Find $\displaystyle 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 $\displaystyle 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 $\displaystyle hcf(q_1~,~q_2)\cdot lcm(q_1~,~q_2)=q_1\cdot q_2$

    so; $\displaystyle 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 $\displaystyle hcf(m~,~n)$ where $\displaystyle m$ , $\displaystyle 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
    Thanks
    1

    LCM

    Hello everyone -

    I don't quite see what the problem is with my solution and the example
    Find $\displaystyle 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 $\displaystyle 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 $\displaystyle q_1 = \frac{m_1}{n_1}$ and $\displaystyle q_2 = \frac{m_2}{n_2}$ and that each fraction is in its lowest terms. In other words $\displaystyle m_1$ and $\displaystyle n_1$ are co-prime, and $\displaystyle m_2$ and $\displaystyle n_2$ are co-prime.

    Then:

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

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

    Then $\displaystyle Kq_1 = \frac{Km_1}{n_1}$

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

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

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

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

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

    $\displaystyle \implies K=n_1 \implies Kq_1 = m_1$

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

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

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

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

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

    Finally, if $\displaystyle q_1$ and $\displaystyle 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:

    $\displaystyle 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 :
    $\displaystyle 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; Jan 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
    Thanks
    1

    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
    Thanks
    1

    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:

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

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

    $\displaystyle 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 $\displaystyle a=hcf(m_1,n_1)$ and $\displaystyle 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.

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

    $\displaystyle n_1n_2Q=Mm_1n_2=Nm_2n_1$

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

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

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

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

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

    $\displaystyle 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
    $\displaystyle 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 $\displaystyle 1/2$ is a multiple of $\displaystyle 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,

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

    Yet,

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

    then $\displaystyle 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
    Thanks
    1

    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
    $\displaystyle 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 $\displaystyle M$ and $\displaystyle N$ such that:

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

    $\displaystyle \implies M$ must be a multiple of $\displaystyle 7$, say $\displaystyle 7m$, and $\displaystyle N$ is a multiple of $\displaystyle 5$, say $\displaystyle 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 $\displaystyle 3m = 4n$. The lowest integer values that satisfy this are $\displaystyle m=4$ and $\displaystyle n=3$, giving $\displaystyle M = 28$, $\displaystyle N= 15$, and $\displaystyle lcm(\frac{3}{7},\frac{4}{5}) = 12$. Note in passing that $\displaystyle lcm(3,4)=12$.

    Example 2
    $\displaystyle 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 $\displaystyle 7$. Look what happens:

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

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

    $\displaystyle 3m = 4n$

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

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

    $\displaystyle M = 2m$ and $\displaystyle N = 5n$

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

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

    again giving $\displaystyle m = 4$ and $\displaystyle n = 3$, but this time $\displaystyle M=8$ and $\displaystyle N=15$, and so $\displaystyle lcm(\frac{3}{14}, \frac{4}{35})= \frac{12}{7}$. (Note that the answer is now $\displaystyle lcm(3,4)$ divided by $\displaystyle 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 $\displaystyle m_1, n_1, m_2$ and $\displaystyle n_2$ one at a time, so that you cover all combinations:


    • $\displaystyle hcf(m_1, m_2) = 1$ and $\displaystyle hcf(n_1, n_2)=1$ (in other words the numerators are co-prime and so are the denominators)
    • $\displaystyle hcf(m_1, m_2) = 1$ and $\displaystyle hcf(n_1, n_2)>1$
    • $\displaystyle hcf(m_1, m_2) > 1$ and $\displaystyle hcf(n_1, n_2)=1$
    • $\displaystyle hcf(m_1, m_2) > 1$ and $\displaystyle 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
    Thanks
    1

    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 $\displaystyle q_1$ and $\displaystyle q_2$ are expressed in their lowest terms; i.e. $\displaystyle m_1$ and $\displaystyle n_1$ are co-prime and $\displaystyle m_2$ and $\displaystyle n_2$ are co-prime. (If not, they should be expressed in their lowest terms by 'cancelling'.) The formula then is:

    $\displaystyle q = \frac{l}{h}$

    where $\displaystyle l = lcm(m_1, m_2)$ and $\displaystyle 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 $\displaystyle l = lcm(m_1,m_2)$ then for some integers $\displaystyle p_1$ and $\displaystyle p_2, l=m_1p_1 = m_2p_2$ if and only if $\displaystyle p_1$ and $\displaystyle p_2$ are co-prime.

    Proof of Lemma 1:

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

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

    In a similar way, we may prove

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

    Proof of formula

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

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

    Then:

    (3) $\displaystyle M$ and $\displaystyle 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:

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

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

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

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

    $\displaystyle M = mp_3$, for some integer $\displaystyle m$.

    Similarly $\displaystyle N = np_4$, for some integer $\displaystyle n$.

    So, from (4):

    $\displaystyle mm_1 = nm_2$

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

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

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

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

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

    $\displaystyle = \frac{lp_3}{hp_3}$

    $\displaystyle = \frac{l}{h}$

    QED

    Grandad
    Last edited by Grandad; Jan 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