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

B A question about Greatest common factor (GCF) ?

  1. Apr 16, 2017 #1
    When we try to find the Greatest common factor (GCF) of two numbers , does it only involve prime factorization ?

    :nb)
     
  2. jcsd
  3. Apr 16, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Yes. The GCF is a product of primes but is not usually a prime itself. Prime factorization of both numbers is the way to find out what the GCF is. If you have the prime factorization of both numbers, it is easy to calculate the GCF.
     
  4. Apr 16, 2017 #3
    Ok , so the same prime factorization is used to find the LCM too , right ?
     
  5. Apr 16, 2017 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Yes.
     
  6. Apr 16, 2017 #5
    Ok , Thanks
     
  7. Apr 16, 2017 #6
    I dare to disagree, Euclid's algorithm or binary GCD are used to find GCD, then LCM(a, b)=a*b/GCD(a, b).
     
  8. Apr 16, 2017 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I stand corrected. I was not familiar with these algorithms. The binary GCD algorithm and Euclidean_algorithm are interesting.
     
  9. Apr 16, 2017 #8
    Ok, i have one more doubt .
    The GCF of two numbers involves prime factorization of those two numbers , then multiply those factors both numbers have in common

    Isnt LCM about finding the least common multiple of two numbers ?

    What does that have anything to do with prime numbers ?
     
  10. Apr 16, 2017 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can find the LCM via LCM(a, b)=a*b/GCD(a, b), if you have the GCD first.
    That is often the most practical way to find the LCM.

    Prime factorization is just one possible way to find the GCD. For large numbers, it can be very time-consuming, and different algorithms can be more efficient.
     
  11. Apr 16, 2017 #10
    Thanks for the information mfb , i am just trying to cover the algebra 1 for dummies book .
    It doesn't have a method like this LCM(a, b)=a*b/GCD(a, b) mentioned in it .
     
  12. Apr 16, 2017 #11

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You'll find that in an "algebra for intelligent students" textbook!
     
  13. Apr 16, 2017 #12
    lol ok , first let me somehow finish this one book properly :wink:
     
  14. Apr 16, 2017 #13

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's still worth understanding why the two are related. The basic argument is:

    ##a = a'g, b = b'g##

    Where ##g## is the GCD of ##a## and ##b## and ##a', b'## are how much bigger ##a## and ##b## are than ##g##.

    For example: if ##a = 42## and ##b = 15##, then ##g = 3## and ##a=14 \times 3, b = 5 \times 3##, hence ##a' = 14, b' = 5##

    Now, the LCM of ##a## and ##b## must have as factors simply ##a', b'## and ##g##, so ##l = a'b'g = a'b = a'gb/g = ab/g##

    You can now see that the LCM is the product of ##a## and ##b##, divided by the GCD.

    In our example:

    ##LCM(42, 15) = \frac{42 \times 15}{3} = 210##
     
  15. Apr 16, 2017 #14
    Thanks for sharing , i will keep this in my mind and maybe someday i will be able to use this advanced method . :nb)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: A question about Greatest common factor (GCF) ?
  1. Greatest common divisor (Replies: 11)

Loading...