Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Greatset Common Divisor (GCD) Questions

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Taiwan
    Posts
    17

    Greatset Common Divisor (GCD) Questions

    Q1) Are the GCD, Greatest Common Factor (GCF) and Highest Common Factor (HCF) all referring to the same thing?

    I'm using the GCD to simplify fractions to their lowest terms. To find the GCD I've been using two methods. The first method is doing prime factorization and multiplying the common prime factors together. The second method is called Euclid's algorithm. Both methods seem slow.

    Q2) Should I be using GCD to simplify fractions? And does using prime factorization have a benefit over Euclid's method as I advance in Algebra or higher math?

    Q3) My book shows the solution below to simply the fraction below.
    3990 = 6* 665 = 665 = 7*95 = 95
    6762 6*1127 1127 7*161 161

    I don't understand how they arrived at the 6 and 7.
    I did prime factorization and wrote out the following. (sorry, i used the , for multiplication on accident)
    3990 = 2,3,7,5,19 = (2,3,7), 5,19 = 95
    6762 2,3,7,7,23 (2,3,7), 7,23 161

    I notice I could multiply 2*3 and arrive at the 6 and 7 like they did, but then that's doing more steps in the method I'm doing.
    So I'd like to know ...

    Q4) Is there is a simpler method they used to arrive at the 6 and 7?

    Also, a further note, using Euclid's Algorithm was one step faster than the prime factorization in this particular problem, plus I didn't have to refer to (or memorize) a table of prime factors.

    Thanks for taking the time to read my post to the end. I hope it's clear and easy to understand.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Greatset Common Divisor (GCD) Questions

    Quote Originally Posted by MrDiedel View Post
    Q1) Are the GCD, Greatest Common Factor (GCF) and Highest Common Factor (HCF) all referring to the same thing?
    Yes.

    Quote Originally Posted by MrDiedel View Post
    Q2) Should I be using GCD to simplify fractions? And does using prime factorization have a benefit over Euclid's method as I advance in Algebra or higher math?
    The further you study math, the fewer numerical calculations you have to do. After you get a solid grasp of how to compute by hand, it becomes less important how you arrive at the numerical answer. Concerning fractions, I usually repeatedly divide the numerator and the denominator by the first suitable number I can find.

    Quote Originally Posted by MrDiedel View Post
    Q3) My book shows the solution below to simply the fraction below.
    3990 = 6* 665 = 665 = 7*95 = 95
    6762 6*1127 1127 7*161 161

    I don't understand how they arrived at the 6 and 7.
    3990 and 6762 are divisible by 6 because they are even and the sum of their digits is divisible by 3. For 7, they probably tried it and found that it divides both numbers. E.g., 665 = 630 + 35 = 7 * 90 + 7 * 5 and 1127 = 1120 + 7 = 7 * 16 + 7 * 1.

    For really big numbers, Euclid's algorithm is more efficient because there are no currently known efficient factorization algorithms. "When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known; an effort concluded in 2009 by several researchers factored a 232-digit number (RSA-768), utilizing hundreds of machines over a span of 2 years. The presumed difficulty of this problem is at the heart of widely used algorithms in cryptography such as RSA" (Wikipedia).
    Thanks from MrDiedel
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    Taiwan
    Posts
    17

    Re: Greatset Common Divisor (GCD) Questions

    emakarov, I really appreicate your answer to question 2 and 3. However, I must confess I have no knowledge of RSA and the following text afterwards. I do conclude however, that they did not use anything other than guesswork to arrive at their 6 and 7 which was the point I wanted to know. As the book was not specific or clear on that point.

    My conclusion,

    I will use Euclid's algorithm for anything that is not apparently obvious to ME. I'm trusting your information based solely on your posts and thanks counts because I don't know you, however you appear to be intelligent and offer sound advice. Thanks again. Have a great day, I know I did!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2013
    From
    India
    Posts
    30
    Thanks
    4

    Re: Greatset Common Divisor (GCD) Questions

    3990/6762
    It is not so simple for find prime factors.
    use GCD by division method
    3990)6762(1
    ----3990
    -----------
    -----2772
    2772)3990(1
    -----2772
    -----------
    ------1218

    1218)2772(2
    -----2436
    -------------
    -----336
    336)1218(3
    ----1008
    ---------
    ---- 210)336(1
    ---------210
    --------------
    -------- 126)210(1
    ----------- 126
    ----------------
    ---------- 84

    84)126(1
    --- 84
    --------
    ----42)84(2
    -------84
    ----------
    ------00
    GCD is 42
    3990/6762
    = (3990 42)/(6762 42)
    = 95/161
    ----
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  2. Common Divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 6th 2010, 11:05 AM
  3. Greastest Common Divisor
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 9th 2009, 01:24 AM
  4. algorithm for common divisor
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: September 24th 2009, 05:36 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 01:08 AM

Search Tags


/mathhelpforum @mathhelpforum