# Math Help - hcf's and lcm's

1. ## 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?

2. ## 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?

3. Hello,

then isn't the answer simply

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

4. 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, $
lcm(q_1, q_2) = lcm(m_1,m_2)
$
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))$?

5. 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.

6. 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.

7. Originally Posted by Showcase_22
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.

8. ## 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?

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.

10. ## Apologies

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

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

Apologies.

11. ## 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?

12. 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

13. Originally Posted by Showcase_22
$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$

14. ## 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.

15. ## 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