# LCM AND HCF

#### Dr.Peterson

##### Elite Member
it can just be a common multiple not a "integer multiple"
"Multiple" in the phrase "common multiple" means "[positive] integer multiple". What are you claiming?

What is the minimality they are saying ?
They are implying that LCM is the minimum no . something like that?
"Least" in LCM means minimum! So of course they are!

And ab/GCD gives a no which should be at least equal or greater than LCM.
They cannot directly say it can be equal to LCM as they are trying to prove that only.
ab/GCD is a multiple of both a and b, so it is a common multiple, so you can conclude that it is greater than or equal to the least common multiple. This is one half of proving that it is the LCM.

I know that as LCM(a,b) and product of a and b are both Common multiples of a and b so I should get r =0 upon dividing ab/LCM as a*b is also a multiple of lcm(a,b) .
You could do it that way; they said it differently. So? The conclusion is the same, that the lcm divides ab.
And as r=0 (0 is a mutliple of every integr)so I know that r is a common multiple of a and b.
But here one can say that then LCM must be 0 as it is the least.
That's not useful to say. "Multiple" is taken to mean "multiple by a positive integer"; "LCM" means least positive multiple, not least integer multiple.
They say this:
By division, we can write
ab = q lcm(a,b)+r where 0≤r<lcm(a,b)​
Because ab and lcm(a,b) are common multiples of a and b, so is r. By the minimality of the lcm, r=0. Therefore, lcm(a,b) divides ab.
What this means is because r = ab-q lcm(a,b), the difference of two integer multiples of both a and b, it must also be an integer multiple of a and b. But since it is less than the least common multiple, it must be zero. (But that doesn't make it the lcm.)

Consequently, ab = q lcm(a,b), which means the lcm divides ab.

Yes, this could also be derived by the fact that the lcm divides every common multiple, and ab is a common multiple; but he is not assuming that to be known.

#### pka

##### Elite Member
It has no relation with other posts
@Dr.Peterson
@JeffM
@pka
Frankly I am put-off by your post.
If you have a further question then post it.
Do not ask us to read a previous post and guess what question you have.
$$LCM\{5,7\}=35$$ but $$LCM(25,35)=175$$ why is that?

#### Saumyojit

##### Full Member
What are you claiming?
ab/ GCD(a,b) is a positive integer multiple of 'a' by "a positive integer" . Right?
That positive integer is " b/GCD(a,b)
Right?

If so as far as I remember
If both the no's are integers (a &b)
Then a=b*n [n is also integer]
a is a multiple of b

If one of the nos is in decimal format ( rational)
12=1.5 *8
Then 12 is a "Integer multiple" of 1.5!
So when are u saying Integer multiple are u saying in general context?

Ok i got it .

#### Dr.Peterson

##### Elite Member
ab/ GCD(a,b) is a positive integer multiple of 'a' by "a positive integer" . Right?
That positive integer is " b/GCD(a,b)
Right?

If so as far as I remember
If both the no's are integers (a &b)
Then a=b*n [n is also integer]
a is a multiple of b

If one of the nos is in decimal format ( rational)
12=1.5 *8
Then 12 is a "Integer multiple" of 1.5!
So when are u saying Integer multiple are u saying in general context?
How are you concluding that a and b (which can be any positive integers) are necessarily multiples of one another? That clearly isn't true.

Yes, we could say that 12 is an integer multiple of 1.5; but in our context we are talking only about integers (a and b). Don't bring non-integers into the discussion! (And I have no idea why you think that affects what we have been saying.)

#### Saumyojit

##### Full Member
How are you concluding that a and b (which can be any positive integers) are necessarily multiples of one another?
a and b I took it individually .it's not in GCD(a,b)context.
forget this.
I understood

#### Saumyojit

##### Full Member
What is the greatest whole number that divides a evenly. Obviously a itself. And by hypothesis a divides c evenly.So the highest common factor is a.
Therefore if a divides c evenly, a is the highest common facto
This part I understood
@Dr.Peterson

@JeffM

If d < b then a * d < c.

Therefore the least common multiple of a and c is c.
Why did you included 'd' in here
Did not understand this para

U did a*b =c understood which meant 'c' is a multiple of a and then u told that least mutliple of c is 'c' , yes understood.
Then u took a positive integer 'd' which when multipled with a will obviously give product less than 'c' as d <b.

How did you concluded from there that LCM of a and c is c.

Last edited:

#### JeffM

##### Elite Member
It is extremely annoying to search back over pages to find what you quote in part so the whole context can be seen. This is especially true about a post that is over 4 months old; I cannot put myself back in the mental context of a post that old without reading everything that went before it. If you have questions about a post, please quote the entire thing and do so promptly.

What follows is the post that you asked the question about in red and my current comments in blue.

Suppose a, b, c, and d are positive whole numbers and that a * b = c

First, note that the realm of discourse is positive integers. When you start introducing fractions or zero, you are completely changing what is being discussed. This is why your jumping around willy-nilly gets you mired in "doubts." Your "doubts" are confusion arising from not sticking to a topic until you have learned it. If you ask a question about least common multiple and highest common factor, you are talking about positive whole numbers and dealing with number theory. Abstract algebra is completely off-topic and will only confuse the issue because abstract algebra is talking about things that may not even be numbers.

Second, a, b, c, and d are supposed to represent ANY positive whole numbers SUBJECT to whatever restrictions are specified. It is frequently helpful when dealing with general propositions to take a a specific example. I am going to restate what we are talking about.

$$\displaystyle \text {Let } a,\ b, c, \text { and } d \text { be any positive whole numbers such that }\\ a * b = c \text { and } d < b.$$

Let's take as our example a = 3, b = 17, c = 51, and d = 5. Now any "doubts" that you may have should be capable of being expressed in an example THAT MEETS THE CONDITIONS SPECIFIED.

We are interested in what are the highest common factor and least common multiple of a and c.

The smallest multiple of c is c * 1 = c.

What I am saying here is that if I multiply c and any number OTHER THAN 1, the product (the multiple) will be larger than c. For example, 2 * 51 = 102 > 51. It's true of course that fifty-one times minus ten is less than fifty-one, BUT WE ARE NOT TALKING ABOUT NEGATIVE NUMBERS. It's also true that fifty-one times zero times is less than fifty-one, BUT WE ARE TALKING ABOUT POSITIVE NUMBERS, and zero is not a positive number. And finally it is true that fifty-one times a proper fraction is less than fifty-one, BUT WE TALKING ABOUT WHOLE NUMBERS.

In other words, because we are talking about positive whole numbers, out of the infinite number of multiples of 51, the smallest, the least, is 51 * 1 = 51. If you have doubts that the general proposition that c * 1 is the least multiple of c when we are talking about positive whole numbers, please give me the specific example that raises a doubt in your mind.

I have not yet claimed that c * 1 is the least COMMON multiple of a and c. We have not yet talked about the multiples of a. There are an infinite number of them. And the list of common multiples of a and c is also infinite.

If d < b then a * d < c.

What am I getting at here? I am going to consider the finite list of multiples of a that involve some positive whole number less than b (the list has only b - 1 items).

d < b \implies a * d < a * b because a is positive.

Therefore a * d < c because a * b = c.

Therefore a * d < c * 1 because c * 1 = c.

Therefore, a * d is a multiple of a, but it is less than c * 1, which is the least multiple of c. Therefore, a*d is not a COMMON multiple of a and c.

But a * b = c = c * 1 and

Therefore the least common multiple of a and c is c.

In my example, a = 3 and b = 17. Let's list the first 16 multiples of 3. 3, 6. 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48. Each of them is smaller than 51 so none of them can be a common multiple of 3 and 51 because the smallest multiple of 51 is 51 itself. So my remark in red above is justified by this example. If you can give me a counter-example, I shall willingly concede that your doubts have some basis.

What is the greatest whole number that divides a evenly. Obviously a itself. And by hypothesis a divides c evenly.

So the highest common factor is a.

Any questions or doubts on those two lines? We can then summarize with:

Therefore if a divides c evenly, a is the highest common factor and c is the lowest common multiple

We do not need to bother with prime factorization at all.

There are many other things we do not have to bother with such as the entire corpus of abstract algebra.

Just grasp what highest and lowest and common mean in context.

The helpers here will try to answer any questions you have about their own posts if you quote those posts fully and pose the questions promptly. It is unreasonable, however, to ask them to clarify what someone else has written. It is reasonable to ask a helper to resolve an apparent contradiction between the helper's post and a cited alternative authority IF YOU ARE SURE THAT THE ALTERNATIVE IS ON TOPIC.

Last edited:

#### Saumyojit

##### Full Member
a * d is a multiple of a, but it is less than c * 1, which is the least multiple of c. Therefore, a*d is not a COMMON multiple of a and c.
That means u took d to show that I will not get from 'a' to 'c' until and unless we make 'a' to go b times from 0 to c .
So the greatest value of d which is 16 cannot help a to reach 'c' if and only if a starts from 0 on the no line.
That is the significance of d . Right?

I have written from 0 to c but not from 3 to c i.e 3 to 51 that's because what I saw as b is 17 so my 17 steps will be
(0-3,3-6,6-9,9-12,12-15,15-18,18-21,21-24..48-51) -> 17 times 'a' is hopping in terms of 3 places each time from 0-51 to reach c.
But if I started from 3-6 ,...48-51 then a would have gone 16 steps or times to meet . right?
the list has only b - 1 items
Only if d=16 .

Last edited:

#### JeffM

##### Elite Member
There are an infinite number of multiples of c. There are an infinite number of multiples of a. And there are an infinite number of COMMON multiples of a and c. We want to find the smallest of the common multiples.

Remember that we have set things up so that a, b, and c are positive whole numbers such that

$$\displaystyle a * b = c \implies a < c.$$

And I hope you are convinced that c * 1 = c is the least multiple of c, meaning the smallest product of c and any positive whole number.

How many multiples of a are there before we reach ANY multiple of c? We can express a multiple of a as a * d. As you say, that means a * d is d steps, each of length a, away from zero. It takes b steps of length a to reach c. If d is less than b, we have not progressed as far as c so any multiple of a and d is less than c, which is the least multiple of c. Therefore a * d is not a common multiple of a and c even though it is a multiple of a.

But a * b = c = c * 1 is a multiple of both a and c. It is a multiple they have in common. It is a common multiple. Moreover, there is no multiple of c less than c so, out of the infinite list of common multiples of a and c, it is the least.

You can simplify the argument to this.

a * b = c by hypothesis.

c = c * 1 means that c is the smallest multiple of c.

And c is also a multiple of a.

Therefore, c is the smallest number that is both a multiple of a and of c.

Thus, c is the least common multiple of a and c.

What in that argument strikes you as questionable?

#### Saumyojit

##### Full Member
What in that argument strikes you as questionable?
From the beginning i didn't have any counter argument but I was not getting why u included a*d part .But I think I got it.

This is just another related picture of one question
If someone says how many positive nos are there divisible by 3 less than equal to 30
Then we will divide 30/3=10
0-3,3-6..27-30
We should not Start our journey of 3 from 3 itself though It kind of tempts me to do so as first multiple of 3 is 3 .
But we are actually starting from zero and hopping 3 places 10 times total to reach 30.
But we don't take 0 as a multiple of 3

Last edited:

#### JeffM

##### Elite Member
From the beginning i didn't have any counter argument but I was not getting why u included a*d part .But I think I got it.

This is just another related picture of one question
If someone says how many positive nos are there divisible by 3 less than equal to 30
Then we will divide 30/3=10
0-3,3-6..27-30
We should not Start our journey of 3 from 3 itself though It kind of tempts me to do so as first multiple of 3 is 3 .
But we are actually starting from zero and hopping 3 places 10 times total to reach 30.
But we don't take 0 as a multiple of 3
No, when we think of multiplication BY A POSITIVE WHOLE NUMBER as repeated steps AWAY from zero, the first step gets us to 3.

And yes if we ask how many positive numbers are divisible by 3 but less than 30, you divide 30 by 3 and then subtract 1 to get 9.

Here they are.

3, 6, 9, 12, 15, 18, 21, 24, 27.

Count them, there are nine of them.

I admit that this is not very mathematical in spirit, but as I said earlier, we can treat arithmetic axiomatically and justify those axioms by experiment. When we are dealing with basic arithmetic, if you cannot think of a counter-example, stop having doubts. You can develop arithmetic from more primitive concepts, but it is very abstruse. It may seem illogical, but mathematicians did great mathematics for millennia before anyone figured out a way to validate the fundamentals of arithmetic except by repeated experiment. You will waste years of work if you try to comprehend the mathematics that logically lies underneath arithmetic before you have developed mathematical intuition that comes from studying elementary algebra, calculus, etc. The history and the psychology do not follow the logical path.

#### Saumyojit

##### Full Member
Another thing I found that when we find the LCM of rational nos or hcf of rational nos ; drawing the venn diagram and showing the prime factorisation of Rational numbers which we generally do for Integrs then we tell that "hcf" is the number which contain the factors in the overlapping region of the venn diagram .
But in the Rational number case we don't get the correct hcf by this method.
I took this two no's (1/4, 1/22) and found out that after drawing venn diagram of each no's prime factorisation that the overlapping region contains 2^-1 as the highest Common factor , but that is purely wrong as the hcf of (1/4, 1/22) is 1/44.
But this way using the notation
π p ^ min(a subscript p , b subscript p) I am getting the correct HCF.
Also I found out one formula to compute
Hcf of fractions= hcf of numerator/LCM of Denom
@Dr.Peterson

#### Saumyojit

##### Full Member
@Dr.Peterson

can you please explain me this
a fraction which is a common multiple of a/b,c/d.
It is the least one
how they are concluding that fraction is a common multiple and then that it is the least.

by the properties of the lcm and gcd of two integers
i know that product of two numbers equal the product of lcm and hcf. How does that fit here

#### JeffM

##### Elite Member
@Dr.Peterson

can you please explain me this
how they are concluding that fraction is a common multiple and then that it is the least.

i know that product of two numbers equal the product of lcm and hcf. How does that fit here
Did you try working through a concrete example?

Try 6/35 and 22/39.

Do it step by step and show us what you get?

#### Saumyojit

##### Full Member
Did you try working through a concrete example?

Try 6/35 and 22/39.

Do it step by step and show us what you get?
I know that if I take two numbers 2/3, 4/5 then lcm 2/3, 4/5 =lcm num/ gcd denom this will work but i am not asking that.
Then the question would not have been asked in Stack .
I was asking for some abstract (algebraic )logical way that how did they say
lcm of numerator of fraction / gcd denom of fraction is a common multiple and least ...

that means we need to assume and this is a part of the proof ?

#### JeffM

##### Elite Member
I know that if I take two numbers 2/3, 4/5 then lcm 2/3, 4/5 =lcm num/ gcd denom this will work but i am not asking that.
Then the question would not have been asked in Stack .
I was asking for some abstract (algebraic )logical way that how did they say
lcm of numerator of fraction / gcd denom of fraction is a common multiple and least ...

that means we need to assume and this is a part of the proof ?
Did you even try to work out concrete examples of what the notation means?

What specifically do you think is being assumed?

#### Saumyojit

##### Full Member
Did you even try to work out concrete examples of what the notation means?