Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Gcd and lcm

  1. Jul 26, 2011 #1

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


    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?
  2. jcsd
  3. Jul 26, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    hi rukawakaede! :smile:
    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? :confused:
  4. Jul 27, 2011 #3
    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.
    Last edited: Jul 27, 2011
  5. Jul 27, 2011 #4

    Yes, so what is the general approach for this?
  6. Jul 27, 2011 #5
    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.
  7. Jul 27, 2011 #6


    User Avatar
    Science Advisor
    Homework Helper

    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 :wink:
  8. Jul 27, 2011 #7
    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?:smile:

    Or can someone provide a counter example where this procedure fails?:smile:
    Last edited: Jul 27, 2011
  9. Jul 27, 2011 #8
    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
  10. Jul 27, 2011 #9

    so do you mean that it is nonsensical to do the gcd for non-integers, in particular rationals?
  11. Jul 27, 2011 #10
    Can you find a rational larger than 1/2 that divides 3 AND 5/2 without remainder?:smile:

    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.:smile:
  12. Jul 27, 2011 #11
    Can you tell me where you encountered the formula??? Taking the gcd in that fashion makes little sense to me :frown: I would like to see the reference to see what exactly they're talking about.
  13. Jul 27, 2011 #12
    Yes: 1, 2, 3/5, etc. all divide 3 and 5/2.
  14. Jul 27, 2011 #13
    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.
  15. Jul 27, 2011 #14
    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.
    Last edited: Jul 27, 2011
  16. Jul 27, 2011 #15
    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.:smile:

    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.:smile:
  17. Jul 27, 2011 #16
    No, they don't, none of them do:smile:
  18. Jul 27, 2011 #17
    Sigh, you again :frown:

    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.
    Last edited: Jul 27, 2011
  19. Jul 27, 2011 #18
    You are missing the point, the point is nobody knows everything there is to know about divisibility.:smile:
  20. Jul 27, 2011 #19
    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.
  21. Jul 27, 2011 #20
    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.:smile:

    I have read many books on abstract algebra.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook