Proving LCM Formula and GCD for Non-Integers

[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