Proving LCM Formula and GCD for Non-Integers

[rukawakaede]

Hi,

I encountered the following formula while reading, can anyone prove this:

$$lcm(a,b)=gcd(a^{-1},b^{-1})^{-1}$$

Also, how could one do the gcd for non-integer?

for example we know that lcm(1/3,2/5)=2. then if we use the formula above then lcm(1/3,2/5)=1/gcd(3,5/2). then gcd(3,5/2) should be 1/2 but it does not make sense (to me at least).
Can anyone explain? Is this depends on which integral domain and its field of fractions that we work on?

 

[tiny-tim]

hi rukawakaede!

… gcd(3,5/2) should be 1/2 but it does not make sense (to me at least).

1/2 divides both 3 (6 times) and 5/2 (5 times)

and nothing higher than 1/2 divides both

so gcd(3,5/2) is 1/2, isn't it? ​

 

[agentredlum]

hi rukawakaede! 1/2 divides both 3 (6 times) and 5/2 (5 times)

and nothing higher than 1/2 divides both

so gcd(3,5/2) is 1/2, isn't it? ​

I have a more simple question, how is lcm(1/3, 2/5) = 2 ?

never mind i figured it out, 2/(1/3) is whole number, 2/(2/5) is whole numbed and 2 is smallest positive integer that works.

 

[rukawakaede]

hi rukawakaede!


1/2 divides both 3 (6 times) and 5/2 (5 times)

and nothing higher than 1/2 divides both

so gcd(3,5/2) is 1/2, isn't it? ​

Yes, so what is the general approach for this?

 

[rukawakaede]

I have a more simple question, how is lcm(1/3, 2/5) = 2 ?

never mind i figured it out, 2/(1/3) is whole number, 2/(2/5) is whole numbed and 2 is smallest positive integer that works.

well, 1/3, 2/3, 1, 4/3, 5/3, 2, ... then 2/5, 4/5, 6/5, 8/5, 2, ...
the lowest common multiple of 1/3 and 2/5 is 2.

 

[tiny-tim]

Yes, so what is the general approach for this?

just use common-sense, really …

find a number that's obviously a divisor of both, and then see if you can make it any larger ​

 

[agentredlum]

Yes, so what is the general approach for this?

I have derived a way, i think it works for all fractions but i am not sure. Here is the procedure.

To find gcd(a/b, c/d) first get (ad)/(bc) then reduce this to lowest terms call it s/t

the gcd(a/b,c/d) is then a/(bs) or b/(ct) they both give the same answer

1) your example: gcd(3, 5/2) get (ad)/(bc) = (3*2)/(5*1) = 6/5 already in lowest terms so

gcd(3, 5/2) = 3/(1*6) or 5/(2*5) both give 1/2

Example2: gcd(4, 12/3) get (ad)/(bc) = (4*3)/(12*1) = 12/12 reduce to 1/1 so

gcd(4, 12/3) = 4/(1*1) or 12/(3*1) both give 4

Example3: gcd(10/12, 15/6) get (ad)/(bc) = (10*6)/(15*12) reduce to (1/3)

gcd(10/12, 15/6) = 10/(12*1) or 15/(6*3) both give 5/6

I will assume you got the hang of it now so I'll just post results

gcd(2/3, 5/7) (2*7)/(3*5)= 14/15 so

gcd(2/3, 5/7) = 2/(3*14) or 5/(7*15) both give 1/21

gcd(3/5, 11/7) 21/55

3/(5*21) or 11/(7*55) = 1/35

gcd(5/6, 17/16) get (5*16)/(6*17)and reduce 40/51

5/(6*40) or 17/(16*51) both give 1/48

Can someone confirm these gcd using computer program?

Or can someone provide a counter example where this procedure fails?

 

[saim_]

GCD for non-integers??! Say we define GCD on rationals; we know all rationals divide all rationals. Infinity would be the GCD for any pair 'a' and 'b' ! :D

 

[rukawakaede]

GCD for non-integers??! Say we define GCD on rationals; we know all rationals divide all rationals. Infinity would be the GCD for any pair 'a' and 'b' ! :D

so do you mean that it is nonsensical to do the gcd for non-integers, in particular rationals?

 

[agentredlum]

GCD for non-integers??! Say we define GCD on rationals; we know all rationals divide all rationals. Infinity would be the GCD for any pair 'a' and 'b' ! :D

Can you find a rational larger than 1/2 that divides 3 AND 5/2 without remainder?

I never heard of this before today so thanks for the post rukawakaede, please don't be too eager to give up on your own question.

 

[micromass]

Hi,

I encountered the following formula while reading, can anyone prove this:

$$lcm(a,b)=gcd(a^{-1},b^{-1})^{-1}$$

Also, how could one do the gcd for non-integer?

for example we know that lcm(1/3,2/5)=2. then if we use the formula above then lcm(1/3,2/5)=1/gcd(3,5/2). then gcd(3,5/2) should be 1/2 but it does not make sense (to me at least).
Can anyone explain? Is this depends on which integral domain and its field of fractions that we work on?

Can you tell me where you encountered the formula? Taking the gcd in that fashion makes little sense to me I would like to see the reference to see what exactly they're talking about.

 

[micromass]

Can you find a rational larger than 1/2 that divides 3 AND 5/2 without remainder?

Yes: 1, 2, 3/5, etc. all divide 3 and 5/2.

 

[micromass]

Ah, perhaps they mean that a rational q divides p if there exists an integer n such that qn=p. That would actually make sense. It's something the book should have mentioned.

 

[saim_]

Can you find a rational larger than 1/2 that divides 3 AND 5/2 without remainder?

I never heard of this before today so thanks for the post rukawakaede, please don't be too eager to give up on your own question.

Yes. Take 10000 for example. It divides both 3 and 5/2. You could define division as micromass suggests in the post above, with the multiplying number 'n' being integer even though all other numbers are rationals, but, that seems like a pretty pointless exercise.

 

[agentredlum]

Yes. Take 10000 for example. It divides both 3 and 5/2. You could define division as micromass suggests in the post above, with the multiplying number 'n' being integer even though all other numbers are rationals, but, that seems like a pretty pointless exercise.

10000 does not divide either of them, try again, with this hint, if you are looking for rationals larger than 5/4 that divide both 3 and 5/2 WITHOUT REMAINDER, you are wasting your time.

When you define 'n' to be integer and all others rational you get gcd of fractions which is something you, micromass, me, and probably many others never heard of before today. IMHO this is not a pointless excercise.

 

[agentredlum]

Yes: 1, 2, 3/5, etc. all divide 3 and 5/2.

No, they don't, none of them do

 

[micromass]

10000 does not divide either of them, try again, with this hint, if you are looking for rationals larger than 5/4 that divide both 3 and 5/2 WITHOUT REMAINDER, you are wasting your time.

Sigh, you again

You are looking at rationals numbers, and in rational number 100000 divides both 3 and 5/2. The result of the division is 3/100000 and 5/200000.
The definition of division in the rationals (or any commutative ring) is classicaly that "a divides b if there exists a c such that ac=b". So according to this definition (which really is the standard definition), you will get that every nonzero number will divide any other number.

It is only when demanding c to be an integer that you will get the division that seems to be used here.

The notion of divisibility is very precisely defined in mathematics. And you MUST follow the definitions ALWAYS.

 

[agentredlum]

Sigh, you again

You are looking at rationals numbers, and in rational number 100000 divides both 3 and 5/2. The result of the division is 3/100000 and 5/200000.
The definition of division in the rationals (or any commutative ring) is classicaly that "a divides b if there exists a c such that ac=b". So according to this definition (which really is the standard definition), you will get that every nonzero number will divide any other number.

It is only when demanding c to be an integer that you will get the division that seems to be used here.

You are missing the point, the point is nobody knows everything there is to know about divisibility.

 

[micromass]

You are missing the point, the point is nobody knows everything there is to know about divisibility.

Can you do me a favor? Pick up an abstract algebra book and actually read through it. If you still disagree with me after that, feel free to discuss it with me.

Or if you are unwilling to do so, look at http://en.wikipedia.org/wiki/Greatest_common_divisor and show me one sentence that supports your point.

You can't just go claiming anything, you know.

 

[agentredlum]

Can you do me a favor? Pick up an abstract algebra book and actually read through it. If you still disagree with me after that, feel free to discuss it with me.

Or if you are unwilling to do so, look at http://en.wikipedia.org/wiki/Greatest_common_divisor and show me one sentence that supports your point.

You can't just go claiming anything, you know.

Do me a favor, when you come across a new idea that seems to make sense, don't close your mind to it because you haven't read about it in a book.

I have read many books on abstract algebra.

 

[micromass]

Do me a favor, when you come across a new idea that seems to make sense, don't close your mind to it because you haven't read about it in a book.

You know that this forum only supports discussions that are published somewhere, you know? So if what you are discussing is not in a book, then it is not allowed here.

I have read many books on abstract algebra.

OK, which ones? Pick any abstract algebra book, and show me a paragraph that supports your point. Shouldn't be too difficult will it?

Also, pick the abstract algebra book that you have read. Look for the section on divisibility in integral domains, and quote the definition of divisibility. Can you do that for me?

 

[agentredlum]

You know that this forum only supports discussions that are published somewhere, you know? So if what you are discussing is not in a book, then it is not allowed here.
OK, which ones? Pick any abstract algebra book, and show me a paragraph that supports your point. Shouldn't be too difficult will it?

Also, pick the abstract algebra book that you have read. Look for the section on divisibility in integral domains, and quote the definition of divisibility. Can you do that for me?

Your idea that something is not correct if it is not in a book is unsatisfactory. rukawakaede will post the title of the book.

You misunderstand me, i have read many abstract algebra books but i never heard of this before today, so obviously it wasn't in any of the books i read. That doesn't make it wrong.

 

[micromass]

Your idea that something is not correct if it is not in a book is unsatisfactory.

It's the way math works. Something is correct only if it is published (or it about to be published). Like it or not.

rukawakaede will post the title of the book.

Nonono, you said something. So you must back it up with references.

You said you already read abstract algebra books, which one?? I probably have that book, so I'll put the quote here.

 

[agentredlum]

It's the way math works. Something is correct only if it is published (or it about to be published). Like it or not.
Nonono, you said something. So you must back it up with references.

You said you already read abstract algebra books, which one?? I probably have that book, so I'll put the quote here.

Look, the definition of divisibility in abstract algebra is constrained to non zero integers but if you loosen the constraint a little bit you get something very interesting. That's all I'm saying. It appears to me you want to dismiss it prematurely.

Two books i read thoroughly were by Mcoy and Gallian. I have read at least 10 others that i don't remember titles now, also read Niven and Zuckerman, Anderson, Posemintere, and many other number theory books, including Recreations in the theory of numbers The Queen of mathematics entertains by Bieler

I don't remember reading about this approach in any of the books i read, like i said before, that is one of the reasons i find it fascinating.

 

[agentredlum]

I think I am wasting my time posting anything. From now on I will just read other peoples posts and figure it out myself.

agentredlum at rest.

 

[micromass]

Look, the definition of divisibility in abstract algebra is constrained to non zero integers but if you loosen the constraint a little bit you get something very interesting. That's all I'm saying.

Yes, you do get something extremely interesting by losening the constraints. But you should always say with which definitions you are working. You can't simultaniously say that I am wrong and refuse to give your definitions. You could at least have said that you were losening the constraints...

It appears to me you want to dismiss it prematurely.

What happened is that I told you what definition I was working with, and you told me that I was wrong. I dismissed nothing.

Two books i read thoroughly were by Mcoy and Gallian. I have read at least 10 others that i don't remember titles now, also read Niven and Zuckerman, Anderson, Posemintere, and many other number theory books, including Recreations in the theory of numbers The Queen of mathematics entertains by Bieler

I don't remember reading about this approach in any of the books i read, like i said before, that is one of the reasons i find it fascinating.

You mean "contemporary abstract algebra" by Gallian, right?? Let me quote that:

The following terminology and notation is convenient. If a and b belong to
a commutative ring R and a is nonzero, we say a divides b (or a is di factor of
b) and write a | b, if there exists an element c in R such that b = ac.[

This is the standard terminology. So with this terminology, 10000 will divide 2/5. In fact, every nonzero number will divide 2/5.

If you're losing constraints and making new definitions, then please say so! If you don't, then this will lead to pointless discussions. I hope you understand that.

 

[saim_]

10000 does not divide either of them, try again, with this hint, if you are looking for rationals larger than 5/4 that divide both 3 and 5/2 WITHOUT REMAINDER...

Remainders don't come up in rational multiplication and division. I understand you are trying to modify it but then you should have defined what you are trying to do instead of having people guess at it. I can't believe you have actually read abstract algebra books and never learned how division is defined on rationals?! That is strange. Pointless debate.

 

[agentredlum]

Remainders don't come up in rational multiplication and division. I understand you are trying to modify it but then you should have defined what you are trying to do instead of having people guess at it. I can't believe you have actually read abstract algebra books and never learned how division is defined on rationals?! That is strange. Pointless debate.

I can't believe you went to grade school and never learned what division is. A child would get the answer before any of you got it. So far in this thread tiny-tim is the only one who understands division.

Of course fractional division can have remainders. Just because you don't know how doesn't mean they don't exist.

 

[agentredlum]

Yes: 1, 2, 3/5, etc. all divide 3 and 5/2.

1 divides 3 but leaves remainder .5 for 5/2

2 leaves remainder 1 for 3 and leaves remainder .5 for 5/2

3/5 divides 3 remainder 0 but leaves remainder .1 for 5/2

Don't just dismiss this as nonsense, PICK UP PENCIL AND PAPER AND DO THE CALCULATIONS!

 

[agentredlum]

What happened is that I told you what definition I was working with, and you told me that I was wrong. I dismissed nothing.

NOOOOOOOO...nooooo...no. You posted solutions first, i told you they were wrong, then you told me what definition you were working with. Look at the posts you cannot rewrite history.

 

[saim_]

I can't believe you went to grade school and never learned what division is. A child would get the answer before any of you got it. So far in this thread tiny-tim is the only one who understands division.

Of course fractional division can have remainders. Just because you don't know how doesn't mean they don't exist.

They don't even teach that in grade school. Remainders are defined for integer division only. Quote one grade school level book that does this :D. For more information see:

Wikipedia: Division
http://en.wikipedia.org/wiki/Division_(mathematics)

You can see remainders are there only in division for integers, not rationals . How you are defining division is fine and understandable but once you understand that this is not the standard way of defining division go back and review the objections that were raised.

 

[agentredlum]

They don't even teach that in grade school. Remainders are defined for integer division only. Quote one grade school level book that does this :D. For more information see:

Wikipedia: Division
http://en.wikipedia.org/wiki/Division_(mathematics)

You can see remainders are there only in division for integers, not rationals . How you are defining division is fine and understandable but once you understand that this is not the standard way of defining division go back and review the objections that were raised.

I never said it was standard, i never said fractional remainders are taught in grade school. Distorting my words is not helping your case. You say i don't know the definition of division, that is incorrect. I say you don't know how to divide. Whether or not you have memorized definitions means little to me. Your insistance that considering gcd between fractions is pointless confirms my point that you do not know how to divide. I also suspect you do not know what a remainder is or could be.

 

[saim_]

I never said it was standard

Then you should define what you mean!

At least you are happy :p

 

[tiny-tim]

Come on guys , it's obvious from the original post that division by an integer is intended …

Hi,

I encountered the following formula while reading, can anyone prove this:

$$lcm(a,b)=gcd(a^{-1},b^{-1})^{-1}$$

Also, how could one do the gcd for non-integer?

for example we know that lcm(1/3,2/5)=2. then if we use the formula above then lcm(1/3,2/5)=1/gcd(3,5/2). then gcd(3,5/2) should be 1/2 but it does not make sense (to me at least).
Can anyone explain? Is this depends on which integral domain and its field of fractions that we work on?

hi rukawakaede!


1/2 divides both 3 (6 times) and 5/2 (5 times)

and nothing higher than 1/2 divides both

so gcd(3,5/2) is 1/2, isn't it? ​

 

[agentredlum]

Then you should define what you mean!

At least you are happy :p

I am not responsible for peoples misunderstandings, i try to make things work instead of throwing around definitions why things shouldn't work.

You would be happy too if you realized, like i have, that your horizons have been expanded. If you realize all those math books you read, not one of them mentioned something so simple and obvious. Instead they tell you what can or can't be done. Gallians book was o-k but Mccoy was a NIGHTMARE, now you know why i am suspicious of abstract algebra, not to mention the fact that Godel proved no mathematical system strong enough to give rise to arithmetic can be completely consistent. Do you see where I'm comming from now? I don't trust the definitions (even though i know many, not all) and I am mildly annoyed anytime someone mentions a definition as if it was 'etched in stone'. I ALWAYS look at any definition with suspicion and my motto is question EVERYTHING.

I felt like i owed you an explanation, thanks for being a good sport.

You know i once said the same thing to a math professor friend of mine and he asked 'what should we do? say to hell with rigor!' and i said 'yes, that's what Euler did, that's what Fermat did and look at what they accomplished. I'm not saying get rid of all rigor, just loosen it up a little bit so you can get something done. Rigor is like a stranglehold on creativity'