Proving LCM Formula and GCD for Non-Integers

[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'

 

[saim_]

@agentredlum: You don't want to define everything, fine, don't do it. It was friendly advice.

 

[micromass]

I am not responsible for peoples misunderstandings

Yes you are. You are making statements that are obviously false. And only after a few posts you explain that you are working with a different definition. You should have explained immediately under what definition you are working with. That is your responsibility.

I can post here that I know for certain that 1+1=0. People will come in arguing with me, showing me references of why this is not true, explaining why it is not true. And only after many posts I will exclaim that I was working in modulo 2. This is pointless, I should have said that immediately.

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.

OK, now you give me the impression that you didn't actually understood the math books you read. And your statement of Godels theorem is also false.

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.

What's not to trust with a definition?? A definition is what it is, a definition of a term. There's nothing to trust here. You may argue that there are better definitions or that some modification makes a more efficient definition. But definitions and axioms are etched in stone. From the moment on that you accept to work in a certain axiom-system, then this axiom system is the truth. If you choose not to work in a certain axiom-system, then it becomes false. Either way is fine, but you need to mention which definitions and axioms you are working with!

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'

Now I think you are not understanding the place of rigor in mathematics. Rigor is very important in mathematics, why? Not because it's fun to be rigorous, but because it is necessary.

When doing mathematical research, there are two important processes that play:
- intuition
- rigor
Intuition is important because it let's you find new results and because it let's you find solutions for problems. However, after you find these solutions, you must always check them with rigor. Why? To see if what you did is not false!
There are a lot of intuitively obvious things that turn out to be false.

 

[agentredlum]

Yes you are. You are making statements that are obviously false. And only after a few posts you explain that you are working with a different definition. You should have explained immediately under what definition you are working with. That is your responsibility.

I can post here that I know for certain that 1+1=0. People will come in arguing with me, showing me references of why this is not true, explaining why it is not true. And only after many posts I will exclaim that I was working in modulo 2. This is pointless, I should have said that immediately.
OK, now you give me the impression that you didn't actually understood the math books you read. And your statement of Godels theorem is also false.
What's not to trust with a definition?? A definition is what it is, a definition of a term. There's nothing to trust here. You may argue that there are better definitions or that some modification makes a more efficient definition. But definitions and axioms are etched in stone. From the moment on that you accept to work in a certain axiom-system, then this axiom system is the truth. If you choose not to work in a certain axiom-system, then it becomes false. Either way is fine, but you need to mention which definitions and axioms you are working with!
Now I think you are not understanding the place of rigor in mathematics. Rigor is very important in mathematics, why? Not because it's fun to be rigorous, but because it is necessary.

When doing mathematical research, there are two important processes that play:
- intuition
- rigor
Intuition is important because it let's you find new results and because it let's you find solutions for problems. However, after you find these solutions, you must always check them with rigor. Why? To see if what you did is not false!
There are a lot of intuitively obvious things that turn out to be false.

Do you see what your rigor is doing to you? YOU ARE STILL ARGUING AGAINST SOMETHING THAT SHOULD HAVE BEEN OBVIOUS TO YOU FROM POST #2

I resign from this nonsense!

http://www.youtube.com/watch?v=ZbNXyfPsPwk&feature=related

Let others decide if i am wrong about Godels theorem, i clearly do not trust your judgement anymore

http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems

http://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html

 

[saim_]

@agentredlum: So because of Godel's theorem we shouldn't be rigorous? You know that theorem is absolutely rigorously proven; everything is defined and all. If rigor could do Godel good, it can sure do us good.

 

[agentredlum]

This is what you should do. You should apologize for posting incorrect solutions too quickly and without thinking. Show a little humility and admit you can't know everything micromass.

 

[agentredlum]

@agentredlum: So because of Godel's theorem we shouldn't be rigorous? You know that theorem is absolutely rigorously proven; everything is defined and all. If rigor could do Godel good, it can sure do us good.

Well it didn't do you any good here did it? You know for people who place so much value on rigor, you guys didn't seem to read post #1 and post #2 and give it ANY rigorous consideration, yet you have the nerve to demand absolute rigor from me.

You can still be rigorous and you can still question everything, even definitions set in boldface type.

Books don't teach you to question them, you learn that through other ways, example working in a math center solving hundreds of problems every day, 6 days a week, with pencil and paper for many years.

 

[micromass]

This is what you should do. You should apologize for posting incorrect solutions too quickly and without thinking. Show a little humility and admit you can't know everything micromass.

Show me when I was incorrect.

Well it didn't do you any good here did it? You know for people who place so much value on rigor, you guys didn't seem to read post #1 and post #2 and give it ANY rigorous consideration, yet you have the nerve to demand absolute rigor from me.

I did give it rigorous consideration:

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.

It is you who starts asserting things without defining anything.

What I don't know is whether you are clueless or deliberatly obfusciating things.

 

[agentredlum]

Show me when I was incorrect

Post # 12 you give incorrect solutions to a problem that should have been obvious from post #2. The fact that you believed the solutions were correct based on your misunderstanding is irrelevent, your solutions were wrong.

To your credit, and i admire this about you, 8 minutes later you figure out what is going on in post #13 but for some reason known only to you, you do not retract the incorrect solutions.

Post # 16 i point out the solutions in post #12 are incorrect so here we are 40 posts later still arguing. If i bruised your ego i apologize. Because that's what it looks like to me we are arguing about.

 

[micromass]

Post # 12 you give incorrect solutions to a problem that should have been obvious from post #2. The fact that you believed the solutions were correct based on your misunderstanding is irrelevent, your solutions were wrong.

To your credit, and i admire this about you, 8 minutes later you figure out what is going on in post #13 but for some reason known only to you, you do not retract the incorrect solutions.

Post # 16 i point out the solutions in post #12 are incorrect so here we are 40 posts later still arguing. If i bruised your ego i apologize. Because that's what it looks like to me we are arguing about.

Well, if you think that my post 12 is incorrect, then I'm afraid that you did not understand me very well. I am of course to blame for that, I should have expressed better what I meant.

Anyway, I'm done discussing to you, since (by your own admission) you are unwilling to listen to rigor and reason.

 

[agentredlum]

Well, if you think that my post 12 is incorrect, then I'm afraid that you did not understand me very well. I am of course to blame for that, I should have expressed better what I meant.

Anyway, I'm done discussing to you, since (by your own admission) you are unwilling to listen to rigor and reason.

I never said that about rigor, i said loosen it up a little bit. You misinterperate every statement i make.

We are not going to resolve this issue between us. Let others decide if your solutions in post 12 are right or wrong.

I am also done discussing with you.

 

[rukawakaede]

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.

Hi micromass,

The name of the book is algebraic theory of numbers by pierre samuel. on page 14.

sorry, i missed this message.

i was wondering if gcd(a,b) is an integer which divides a and b? so if a and b are not integers, how could we do gcd of such numbers? if there is no way or it is meaningless to do gcd of rationals which are not integers, then the formula is not well defined. Could you comment further?

 

[rukawakaede]

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.

the book does not specific the domains, just a general integral domain and its field of fractions.

 

[micromass]

the book does not specific the domains, just a general integral domain and its field of fractions.

Yes, I looked in the book and I saw that. But in the case of the integers, it reduces to that.

Hi micromass,

The name of the book is algebraic theory of numbers by pierre samuel. on page 14.

sorry, i missed this message.

i was wondering if gcd(a,b) is an integer which divides a and b? so if a and b are not integers, how could we do gcd of such numbers? if there is no way or meaningless to do gcd of rationals which are not integers, then the formula is not well defined. Could you comment further?

The key concept here is divisibility. Let me quote from the book

Let A be an integral domain, K its field effractions, x and y elements of K. We shall
say that x divides y if there exists a e A such that y = ax.

So divisibility is well defined by this. So a fraction q divides a fraction p if p/q is in the integral domain.

Now, how is a gcd defined. Well, a is called a gcd of b and c if

• a|b and a|c
• If d|b and d|c, then d|a

So, for example gcd(1/2,1/3)=1/6, since

• 1/6 divides 1/2, because (1/2)/(1/6)=3 is an integer
• 1/6 divides 1/3, because (1/3)/(1/6)=2 is an integer
• If 1/a divides 1/2 and 1/6, then a/2 and a/3 are integers, so a must be a multiple of 6. This means that 1/a will always divide 1/6

In general, if you are asked to find the gcd of two elements, then you should find all its divisors and see if there is a greatest one. This will be the gcd.

In the case of rational numbers, I think we can do something of the following to find the gcd. I'll do an example:

Take rationals 60/7 and 8/42. Take the prime decomposition of these numbers:

\frac{2^2*3*5}{7}~\text{and}~\frac{2^2}{3*7}

take the gcd of the numerators and the lcm of the denominator, this yields

\frac{2^2}{3*7}=\frac{4}{21}

this is how to find the gcd of 60/7 and 8/42.

So in general I conjecture that

gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}

I would be pleased if somebody would check this formula for me and tell me if it is indeed correct.

 

[agentredlum]

Try gcd(30/7, 8/42) your method gives 2/42 or 1/21

Try gcd(30/7, 4/21) your method gives 2/21

8/42 = 4/21 but 1/21 does not equal 2/21



You can fix this if you reduce all fractions before computing but that does not gaurantee there are no other difficulties with your method.

I invite everyone to test my method in post #7

 

[rukawakaede]

Yes, I looked in the book and I saw that. But in the case of the integers, it reduces to that.



The key concept here is divisibility. Let me quote from the book



So divisibility is well defined by this. So a fraction q divides a fraction p if p/q is in the integral domain.

Now, how is a gcd defined. Well, a is called a gcd of b and c if

• a|b and a|c
• If d|b and d|c, then d|a

So, for example gcd(1/2,1/3)=1/6, since

• 1/6 divides 1/2, because (1/2)/(1/6)=3 is an integer
• 1/6 divides 1/3, because (1/3)/(1/6)=2 is an integer
• If 1/a divides 1/2 and 1/6, then a/2 and a/3 are integers, so a must be a multiple of 6. This means that 1/a will always divide 1/6

In general, if you are asked to find the gcd of two elements, then you should find all its divisors and see if there is a greatest one. This will be the gcd.

In the case of rational numbers, I think we can do something of the following to find the gcd. I'll do an example:

Take rationals 60/7 and 8/42. Take the prime decomposition of these numbers:

\frac{2^2*3*5}{7}~\text{and}~\frac{2^2}{3*7}

take the gcd of the numerators and the lcm of the denominator, this yields

\frac{2^2}{3*7}=\frac{4}{21}

this is how to find the gcd of 60/7 and 8/42.

So in general I conjecture that

gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}

I would be pleased if somebody would check this formula for me and tell me if it is indeed correct.

A counterexample to the formula
gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}
is:
a=2, b=4, c=4, d=8

gcd(a,c)=2
lcm(b,d)=8
gcd(a,c)/lcm(b,d)=1/4

but gcd(a/b,c/d)=gcd(1/2,1/2)=1/2

Moreover, you can see the error if you investigate the formula further:
gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}
gcd(ad,cb)=gcd(a,c)\cdot gcd(b,d)
this is certainly not true: take the same example as above.

 

[rukawakaede]

Try gcd(30/7, 8/42) your method gives 2/42 or 1/21

Try gcd(30/7, 4/21) your method gives 2/21

8/42 = 4/21 but 1/21 does not equal 2/21



You can fix this if you reduce all fractions before computing but that does not gaurantee there are no other difficulties with your method.

I invite everyone to test my method in post #7

Could you make it in an elegant single formula? and explain or prove how it works?

 

[agentredlum]

Could you make it in an elegant single formula? and explain or prove how it works?

I'll post the procedure without examples, however, i haven't proved it yet

gcd(a/b, c/d)

1) compute (ad)/(bc)

2) reduce (ad)/(bc) call it x/y

3) a/(bx) is the gcd

Thats it, you are done.

NOTE* I derived it but i cannot be sure that i did not make a mistake in the derivation. I used a subtle point in the derivation of step 2. I can post the derivation but it would be about 20 lines long. Give me a few hours to check my work.

 

[agentredlum]

Here is the proof as requested by rukawakaede, if I made a mistake, i apologize.

Let us consider a, b, c, d, p, q, positive integers.

gcd(a/b, c/d) = p/q

This means there is a natural number e such that e(p/q) = a/b

Also there is a natural number f such that f(p/q) = c/d

e and f must be coprime because if they had a common factor p/q would not be the gcd(a/b, c/d)

e/f = (ad)/(bc)

reduce (ad)/(bc) and call it x/y

e/f = x/y

because e,f are coprime and x,y are coprime

e = x and f = y

e(p/q) = x(p/q) = a/b

p/q = a/(bx) = gcd(a/b, c/d)

f(p/q) = y(p/q) = c/d

p/q = c/(dy) = gcd(a/b, c/d)



NOTE* The reduction and coprime is necessary because if k/l = m/n then we CANNOT say k = m and l = n
but if both fractions are in lowest terms, then it MUST be that k = m and l = n. This is why i can state without fear e =x and f = y. That is the key to this derivation and the subtle part i mentioned giving me trouble

 

[micromass]

A counterexample to the formula
gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}
is:
a=2, b=4, c=4, d=8

gcd(a,c)=2
lcm(b,d)=8
gcd(a,c)/lcm(b,d)=1/4

but gcd(a/b,c/d)=gcd(1/2,1/2)=1/2

Moreover, you can see the error if you investigate the formula further:
gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}
gcd(ad,cb)=gcd(a,c)\cdot gcd(b,d)
this is certainly not true: take the same example as above.

Yes, but when I said to take the prime factorization of the fractions, I did mean to take numerator and denominator coprime! Perhaps I should have mentioned this.

So, if a and b are coprime and if c and d are coprime, then

gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}

Let's prove this:

• gcd(a,c)/lcm(b,d) divides a/b. Indeed:
  
  \frac{a/b}{gcd(a,c)/lcm(b,d)}=\frac{a lcm(b,d)}{b gcd(a,c)}
  
  and this is an integer since gcd(a,c) divides a, and b divides lcm(b,d).
  
• gcd(a,c)/lcm(b,d) divides c/d. Analogous.
• The crucial part: say that e/f (with e and f coprimeà divides both a/b and c/d. This means that
  
  \frac{af}{be}~\text{and}~\frac{cf}{de}
  
  are natural numbers. Since b and a are coprime, this means that b will divide f. Since e and f are corpime, this will mean that e will divide a. Analogously, we get that
  
  b and d will divide f and e will divide a and c,
  
  thus lcm(b,d) will divide f and e will divide gcd(a,c). Which means that e/f will divide gcd(a,c)/lcm(b,d), like desired.

So (unless somebody found a mistake anywhere), this means that the formula

gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}

does hold (provided of course that we reduce a/b and c/d such that the factors are coprime).

 

[micromass]

Could you make it in an elegant single formula? and explain or prove how it works?

His formula apparently comes down to

gcd(a/b,c/d)=\frac{gcd(ad,bc)}{bd}

and it works! Nice formula agentredlum!

 

[agentredlum]

His formula apparently comes down to

gcd(a/b,c/d)=\frac{gcd(ad,bc)}{bd}

and it works! Nice formula agentredlum!

Thanks micromass, you did very good work too.

 

[agentredlum]

I feel an obligation to point out that my procedure gcd(a/b, c/d) = a/(bx) or c/(dy) does not work if a = 0 or c = 0 so if one were to compute gcd(0/1, 3/2) using my procedure they would get 0/0 or 1/2 both incorrect. However, we know what the gcd is when one of the numbers is zero, its the OTHER number so no computations are necessary.

Nevertheless this fact makes me a little uneasy.

Your generalization of my procedure does not suffer from this, so well done!

Glad i said 'let us consider positive integers' in my proof. Years of algebra have taught me to avoid zero like the plague.

 

[Emma121]

Albert

 

[agentredlum]

Einstein

 

[agentredlum]

513131aba