# Gcd and lcm

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?

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)

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.

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)

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

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).

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!!

Last edited:
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.

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.

Albert

Einstein

513131aba