LCM AND HCF

[Dr.Peterson]

Let's get that down to a size I can read all at once rather than filling two screens:

a subscript p and b subscript p I know it represents each exponent of the each factors but how does the min and max of a subscript p and b subscript p process works.(4,6) take this eg
Why they're adding max of X,y and min of x,y?

If x=4 and y=6, then min(4,6) = 4, and max(4,6) = 6, right?

So min(x, y) + max(x, y) = 4 + 6 = x + y. One of the numbers has to be the min and the other has to be the max (unless the numbers, are the same, in which case the min and max are the same), so the sum is just the sum of the two numbers.

What you show here is the formal (and far less comprehensible) way to explain the standard method for finding the LCM and GCD using prime factorizations, as stated by pka in post #11.

I can't say for sure why they add them, without seeing what they do next, but I imagine they are using this to prove that LCM(a, b) * GCD(a, b) = ab. Since, once again, you failed to help us out by telling us where to find it, I searched and found it here in Wikipedia. (Why doesn't that surprise me?) And my guess was right. Do you see how they got there?

 

[JeffM]

I have not a clue. You gave us a subordinate clause, but not the independent clause.

 

[Saumyojit]

How does the min and max of " a subscript p and b subscript p " work when it is on the power of the capital pie notation.
HCF(a,b)=HCF(4,6)=π p ^ min(a subscript p , b subscript p)
Now 4 =π p ^ (a subscript p)
=2^2
6=π p ^ (b subscript p)
=2^1 * 3^1
now can you show me how the HCF notation using Min will work or how it will extract the factor

 

[Saumyojit]

HCF(4,6)=π p ^ min(a subscript p , b subscript p)
Now 4 =2^2
6=2^1* 3^1show me how the HCF notation using Min will work or how it will extract the factor

4 =2^2
6=2^1* 3^1

now the HCF notation
π p ^ min(a subscript p , b subscript p) says that HCF of (4,6) is 2.

Writing in terms of capital pie notation--> 2(HCF) = 2^{min(2,1)}
a subscript p is '2' as it is exponent value in 4 and b subscript p is '1' as it is the exponent value in 2 . So we are taking min of 2,1 which is 1 .
so HCF '2'= 2^1 .
its just a way of expressing.

but I didn't get why did they add X and y

 

[Dr.Peterson]

How does the min and max of " a subscript p and b subscript p " work when it is on the power of the capital pie notation.
HCF(a,b)=HCF(4,6)=π p ^ min(a subscript p , b subscript p)
Now 4 =π p ^ (a subscript p)
=2^2
6=π p ^ (b subscript p)
=2^1 * 3^1
now can you show me how the HCF notation using Min will work or how it will extract the factor

Under the capital Pi is the letter p, which here is short for "all primes p". So the product is taken over all primes, which really is only over the primes that are factors of a or b, namely 2 and 3 for your example.

You have

4 = 2^2 * 3^0
6 = 2^1 * 3^1

So the gcd (your "HCF") is the product of 2^min(2, 1) * 3^min(0, 1) = 2^1 * 3^0 = 2

now the HCF notation
π p ^ min(a subscript p , b subscript p) says that HCF of (4,6) is 2.

Writing in terms of capital pie notation--> 2(HCF) = 2^{min(2,1)}
a subscript p is '2' as it is exponent value in 4 and b subscript p is '1' as it is the exponent value in 2 . So we are taking min of 2,1 which is 1 .
so HCF '2'= 2^1 .
its just a way of expressing.

but I didn't get why did they add X and y

The part with x and y is stating a property of max and min that they then apply to a_p and b_p: [MATH]\min(a_p,b_p)+\max(a_p,b_p)=a_p+b_p[/MATH], so that the product of the gcd and the lcm is the product over all primes of [MATH]p^{a_p+b_p} = p^{a_p}p^{b_p}[/MATH]. This shows that the product of gcd and lcm is ab.

 

[Saumyojit]

[https://mathworld.wolfram.com/LeastCommonMultiple.html]

Underscore means "Subscript"

Let m be a common multiple of a and b so that
m=ha=kb.

Write a=a_1GCD(a,b) and b=b_1GCD(a,b), where a_1 and b_1 are relatively prime by definition of the greatest common divisor GCD(a_1,b_1)=1. Then ha_1=kb_1, and from the division lemma (given that ha_1 is divisible by b_1 and GCD(b_1,a_1)=1), we have h is divisible by b_1, so

h=nb_1
m=ha=nb_1a=n(ab)/(GCD(a,b)).

The smallest m is given by n=1,

LCM(a,b)=(ab)/(GCD(a,b)),

so
GCD(a,b)LCM(a,b)=ab

I got that they are trying to prove .
Now if I take a=4 b=3 ( Co prime) then everything is fine but taking a and b (non co prime) a=4 b=6 then in this "ha_1=kb_1"
Part I cannot equate as a is not equal to a_1 and b is not equal to b_1.
1:Why a and b have to be co prime ?
2: Why they have broke the original no's like this a=a_1GCD(a,b)?

 

[Dr.Peterson]

Now if I take a=4 b=3 ( Co prime) then everything is fine but taking a and b (non co prime) a=4 b=6 then in this "ha₁=kb₁"
Part I cannot equate as a is not equal to a₁ and b is not equal to b₁.
1:Why a and b have to be co prime ?
2: Why they have broke the original no's like this a=a₁GCD(a,b)?

0. What do you mean by "part 1" and why do you say it "cannot equate"?
1. No, the whole point is that a and b need not be coprime. Why do you say they must be?
2. That's part of the proof! They've divided out the GCD in order to get a pair of coprime numbers, a₁ and b₁.

Let's work through your example, letting a = 4, b = 6, and m = 36, which is a common multiple of 4 and 6 (but not the LCM).

Then 36 = 4h = 6k, where h = 9 and k = 6.

Since GCD(4, 6) = 2, we can write a = 4 = 2*2 and b = 6 = 3*2, where a₁ = 2, and b₁ = 3. These numbers a₁ = 2, and b₁ = 3 are relatively prime (coprime) as they say. Are you clear on that?

Then ha₁ = 9*2 = 18, and kb₁ = 6*3 = 18, which, as they say, are equal. Therefore the division lemma implies that h = 9 is divisible by b₁ = 3, as in fact it is.

This implies that h = nb₁, that is, 9 = 3n for some integer n (namely 3), as they say.

And m = ha = nb₁a = n(ab)/(GCD(a,b)), that is, 36 = 9*4 = (3*3)*4 = 3*(4*6)/2, which is true.

So, what are you saying is wrong in this case??

Working with a specific example like this can be a useful way to gain an understanding of what someone is saying in general.

 

[Saumyojit]

http://mathforum.org/library/drmath/view/62543.html

In this link Where a|c reads "a divides c," the definition of c = LCM{a,b} is:

i) a|c and b|c

ii) if a|d and b|d, then c|d

d=common multiple of a and b

Now suppose that c = LCM{3,2} = 0. Then let d = 6. We have 3|d and 2|d.
But 0 = c does not divide d, since no number m exists such that
m|0 = 6 = d

c doesn't divide d this I understood ( d/c or 6/0) but what is this 'm'
Why they have written this 0 by m =6.

In the set N of natural numbers with zero, it can be proved from the
definition of LCM that 0 is not the least common multiple of any finite
subset of N, though zero is the least common multiple of N itself, since
(i) holds for all elements of N and (ii) holds for d = 0 only.

i don't understand this paragraph.

 

[Dr.Peterson]

c doesn't divide d this I understood ( d/c or 6/0) but what is this 'm'
Why they have written this 0 by m =6.

Did you miss the entire context? The discussion is, as mentioned later, counterfactual -- that is, supposing a different definition of LCD, which would allow 0 as a common multiple. And this comment is from a reader who brought in yet another definition, contrary to the discussion he was commenting on. Please read the answer he was given! Or just ignore the whole thing, since it is answering a false supposition, not showing things you should be thinking. (Later in the discussion more advanced ideas like "commutative rings" are brought up, which are beyond what you want to be learning, but at the end I summarized what was going on.)

i don't understand this paragraph.

For the same reason, you don't need to. He is working from his (more advanced) definition, and talking about the LCM of an infinite set of numbers, which is not really valid. In any case, all you need to know is that the LCD of two nonzero numbers is not 0.

 

[Saumyojit]

https://math.stackexchange.com/questions/27719/what-is-gcd0-a-where-a-is-a-positive-integer

I was seeing GCD (a,0) .
I feel that according to this notation --> HCF= π p^(min(a subscript p , b subscript p) )
1: HCF(0,8) = 1 => 0= 2^0 ; 8=2^3 (PRIME factorization)
π p_1 ^(min( a subscript p , b subscript p) ) -> 2 ^(min( 0,3) ) -> 2^0-> 1
hcf comes out as '1' <-- how this logic is wrong?

2: HCF(0,8)=8 from the logic that 8 ( gcf must exactly divide two nos although in 0/8 there is nothing to divide) divides both 8 and 0. And nos { 1,2,4} these are Common divisors .


In the site I saw the second condition of divisor to be greatest . What is this 'c' they have used ?
How will i choose c in order to check gcd(a,b) has come right or wrong .
What i feel is that 'c' should be any common divisor of (a,b) which should be less than equal to gcd. Right?

Why did i said less than gcd thats becoz Suppose gcd(4,8) is 4 so it passes the first condition and now coming to second condition i can choose c= {1,2,4} which will pass the second condition but if i chose c=8 then 2nd condition fails which tells me that gcd (4,8)=4 which is wrong .

Now in gcd(0,8) not equals to 1 where they proved it wrong by saying in the second condition that c=8 ;
8 | 0,8 => 8| gcd(0,8)=1/8 is not under Integer domain . So gcd(0,8) not equal to 1
But they could have chose c=1 by which in the 2nd condition would have looked like this :
1|0,8 =>1|gcd(0,8) =1 . So gcd (0,8) =1 .
Which brings me back to the doubt " what is c , how should we choose it "

Now in the line "Put c= gcd(a,b) for (1) "
is he telling to substitute gcd (a,b) in the second condt written using biconditional form.
c | a,b <=> c | gcd(a,b) ; after substituting in place of c i get gcd(a,b) | a,b <=> gcd(a,b) | gcd(a,b)
Am i correct? And why they are telling this .

Also in this line " Notice c|a,0<->c|a so gcd(a,0) =a "
I dont get it how he reached to a conclusion that " so gcd(a,0) =a"

I know -> means implication and <-> means if and only if .

 

[Dr.Peterson]

I was seeing GCD (a,0) .
I feel that according to this notation --> HCF= π p^(min(a subscript p , b subscript p) )
1: HCF(0,8) = 1 => 0= 2^0 ; 8=2^3 (PRIME factorization)
π p_1 ^(min( a subscript p , b subscript p) ) -> 2 ^(min( 0,3) ) -> 2^0-> 1
hcf comes out as '1' <-- how this logic is wrong?

It is not true that 0 = 2^0!

This whole notation doesn't apply, because 0 can't be written as a product of primes.

 

[Saumyojit]

Please also see the other parts of the eagerly waiting for reply

I thought if nothing is there then we take '1' as it represents multiplicative identity ( empty product).

 

[Dr.Peterson]

Please also see the other parts of the eagerly waiting for reply

I thought if nothing is there then we take '1' as it represents multiplicative identity ( empty product).

Yes, so 2^0 is 1, not 0!

Most of the answers on the page you referred to are far above your level. You don't need to understand them.

The better question is, why are you interested in the GCD of a number and 0? What do you want to use it for? That would determine what kind of answer is appropriate.

 

[Saumyojit]

In the site I saw the second condition of divisor to be greatest . What is this 'c' they have used ?
How will i choose c in order to check gcd(a,b) has come right or wrong .
What i feel is that 'c' should be any common divisor of (a,b) which should be less than equal to gcd. Right?

Why did i said less than gcd thats becoz Suppose gcd(4,8) is 4 so it passes the first condition and now coming to second condition i can choose c= {1,2,4} which will pass the second condition but if i chose c=8 then 2nd condition fails which tells me that gcd (4,8)=4 which is wrong .

Now in gcd(0,8) not equals to 1 where they proved it wrong by saying in the second condition that c=8 ;
8 | 0,8 => 8| gcd(0,8)=1/8 is not under Integer domain . So gcd(0,8) not equal to 1
But they could have chose c=1 by which in the 2nd condition would have looked like this :
1|0,8 =>1|gcd(0,8) =1 . So gcd (0,8) =1 .
Which brings me back to the doubt " what is c , how should we choose it "

Now in the line "Put c= gcd(a,b) for (1) "
is he telling to substitute gcd (a,b) in the second condt written using biconditional form.
c | a,b <=> c | gcd(a,b) ; after substituting in place of c i get gcd(a,b) | a,b <=> gcd(a,b) | gcd(a,b)
Am i correct? And why they are telling this .

Also in this line " Notice c|a,0<->c|a so gcd(a,0) =a "
I dont get it how he reached to a conclusion that " so gcd(a,0) =a"

I know -> means implication and <-> means if and only if .

I was wondering what could be the GCD of a and 0 so went to stack.
Just explain the given part.
I think I can understand.
Just the given questions please reply

 

[Saumyojit]

In the site I saw the second condition of divisor to be greatest . What is this 'c' they have used ?
How will i choose c in order to check gcd(a,b) has come right or wrong .
What i feel is that 'c' should be any common divisor of (a,b) which should be less than equal to gcd. Right?

Why did i said less than gcd thats becoz Suppose gcd(4,8) is 4 so it passes the first condition and now coming to second condition i can choose c= {1,2,4} which will pass the second condition but if i chose c=8 then 2nd condition fails which tells me that gcd (4,8)=4 which is wrong .

Now in gcd(0,8) not equals to 1 where they proved it wrong by saying in the second condition that c=8 ;
8 | 0,8 => 8| gcd(0,8)=1/8 is not under Integer domain . So gcd(0,8) not equal to 1
But they could have chose c=1 by which in the 2nd condition would have looked like this :
1|0,8 =>1|gcd(0,8) =1 . So gcd (0,8) =1 .
Which brings me back to the doubt " what is c , how should we choose it "

Now in the line "Put c= gcd(a,b) for (1) "
is he telling to substitute gcd (a,b) in the second condt written using biconditional form.
c | a,b <=> c | gcd(a,b) ; after substituting in place of c i get gcd(a,b) | a,b <=> gcd(a,b) | gcd(a,b)
Am i correct? And why they are telling this .

Also in this line " Notice c|a,0<->c|a so gcd(a,0) =a "
I dont get it how he reached to a conclusion that " so gcd(a,0) =a"

I know -> means implication and <-> means if and only if .

@JeffM please see and reply only the given questions.
When I asked the questions I know I can understand .
Before you guys go offline please reply or I will have to wait another 8 hrs

 

[Dr.Peterson]

I was wondering what could be the GCD of a and 0 so went to stack.
Just explain the given part.
I think I can understand.
Just the given questions please reply

Once again, you are trying to read something that just isn't written clearly, at least not clearly enough for you to figure out. It's very terse. With effort, I can see what he is saying, but this is not something to try to learn from. What you are doing is like a baby trying to get his nutrition from a steak; he'll either choke, or cut himself on the knife.

When he says, "c∣a,b ⟹ c∣gcd(a,b)", this is a conditional statement that says, "if c is a divisor of a and b, then c divides the gcd". In other words, every natural number c that divides a and b also divides the gcd. So then, he is defining gcd(a, b) as the (unique) number that (1) is a divisor of both a and b [that is, a common divisor], and (2) is divisible by every other common divisor (or rather, by every common divisor, including itself).

So c can be any number at all. But the conditional statement applies to any number that is a common divisor. Also, you're misunderstanding the role of c: c is not a candidate for the gcd; rather, it's any common divisor, which you are in effect using to test whether a claimed gcd really is.

In the case of gcd(4,8), you know that 8 is not the gcd because it is not a divisor of 4 (which is the first condition). You don't get to the second condition at all. On the other hand, if you thought that 2 might be the gcd, you would find that it passes that first condition (it is a divisor of both 4 and 8), but when you test all other divisors c, you find that for c=4, it divides both 4 and 8 but does not divide 2, so 2 fails the second condition.

The gcd is, instead, 4, because (1) it is a common divisor, and (2) any common divisor (namely 1, 2, 4) divides 4.

What's going on with this definition is that we replace a literal "greatest" (that any other common divisor must be less) with divisibility, so that we can apply the concept of gcd to entities that have no "less than". (This is part of the more advanced project of generalizing mathematical concepts that you have run across (and tripped over) before when you saw "*" being used to mean any operation.)

Other things you ask are either misunderstandings, or should be cleared up when you understand what is really being said.

But here's why gcd(a, 0) = a: a is a divisor of both a and 0; and any number ("c") that divides both a and 0 divides a. Both parts are obvious. [What's lacking is a proof that by his definition the gcd is unique, so there can't be any other number that passes the test.]

Frankly, it's a lot of work (and time) to "cut up your meat for you" like this. In a way it's interesting to do so, but it is also irritating to have you demand that I spend this much time on you. You need to stop ordering steak and demanding that people cut it for you, until you have all your teeth and learn to use a knife safely! This is why I recommend that, like WIkipedia, you not try to use StackExchange as a learning tool. It has a different purpose.

 

[JeffM]

For heaven’s sake, this is post #39. WHAT QUESTIONS? I am not a mindreader to know what you wish answered.

 

[JeffM]

It’s midnight. I’m going to bed.

 

[Saumyojit]

Now in the line "Put c= gcd(a,b) for (1) "
is he telling to substitute gcd (a,b) in the second condt written using biconditional form.
c | a,b <=> c | gcd(a,b) ; after substituting in place of c i get gcd(a,b) | a,b <=> gcd(a,b) | gcd(a,b)
Am i correct?

I think i am right as u said

he is defining gcd(a, b) as the (unique) number that (1) is a divisor of both a and b [that is, a common divisor], and (2) is divisible by every other common divisor (or rather, by every common divisor, including itself).

which is matching my view after susbtiton of gcd(a,b) in place of c in second equation
gcd(a,b) | a,b <=> gcd(a,b) | gcd(a,b)

you're misunderstanding the role of c

i got it

What's going on with this definition is that we replace a literal "greatest" (that any other common divisor must be less) with divisibility, so that we can apply the concept of gcd to entities that have no "less than"

Which definition : this one -> c | a,b => c | gcd(a,b).
I dont understand "we replace a literal "greatest" (that any other common divisor must be less) with divisibility, so that we can apply the concept of gcd to entities that have no "less than"
can u explain it to me with a eg.
What entities ?
Please use simple english .

Other things you ask are either misunderstandings

Which one? can u highlight it please.


I need to understand this . I spent from morning 9 am to 5pm . But still these doubts are elft

 

[Dr.Peterson]

Which definition : this one -> c | a,b => c | gcd(a,b).
I dont understand "we replace a literal "greatest" (that any other common divisor must be less) with divisibility, so that we can apply the concept of gcd to entities that have no "less than"
can u explain it to me with a eg.
What entities ?
Please use simple english .

I can't. As I said, this is related to more advanced math that you are not ready to understand.

Which one? can u highlight it please.
I need to understand this . I spent from morning 9 am to 5pm . But still these doubts are elft

No, I refuse to say more. You need to let it go. Obsessions are not good.