Gcd and lcm

  • #51
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

:biggrin:

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:smile:
Could you make it in an elegant single formula? and explain or prove how it works?
 
  • #52
460
0
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.:smile:
 
  • #53
460
0
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)

:smile:

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 :smile:
 
  • #54
22,097
3,278


A counterexample to the formula
[tex]gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}[/tex]
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:
[tex]gcd(a/b,c/d)=\frac{gcd(a,c)}{lcm(b,d)}[/tex]
[tex]gcd(ad,cb)=gcd(a,c)\cdot gcd(b,d)[/tex]
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

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

Let's prove this:

  • gcd(a,c)/lcm(b,d) divides a/b. Indeed:

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

    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

    [tex]\frac{af}{be}~\text{and}~\frac{cf}{de}[/tex]

    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

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

does hold (provided of course that we reduce a/b and c/d such that the factors are coprime).
 
  • #55
22,097
3,278
Could you make it in an elegant single formula? and explain or prove how it works?
His formula apparently comes down to

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

and it works! Nice formula agentredlum!! :approve:
 
Last edited:
  • #56
460
0
His formula apparently comes down to

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

and it works! Nice formula agentredlum!! :approve:
Thanks micromass, you did very good work too.:approve::smile:
 
  • #57
460
0
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.:smile:
 
  • #58
1
0
Albert
 
  • #59
460
0
Einstein
 
  • #60
460
0
513131aba
 

Related Threads for: Gcd and lcm

  • Last Post
Replies
3
Views
10K
  • Last Post
Replies
2
Views
4K
Replies
2
Views
3K
Replies
6
Views
9K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
1
Views
2K
Top