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

Abtract Algebra Sanity Check

  1. Oct 27, 2004 #1
    Hello out there!

    I'm working a problem where I need to find the greatest common divisor and the least common multiple for integer pairs. I then need to express the gcd as a linear combination. I could use a sanity check to make sure I'm on the right track.

    I need to find the gcd and lcm of the integer pair: 175 and 35

    By visual inspection, I "see" the answers, but working it out…

    The gcd: [tex] (175,35) = \prod_i p_i^{min(\alpha_i,\beta_i)}[/tex]

    [tex] 175 = 5^1\cdot35 = 5^1\cdot5^1\cdot7^1 = 5^2\cdot7^1[/tex]

    [tex] 35 = 5^1\cdot7^1[/tex]

    [tex] (175,35) = 5^1\cdot7^1 = 35[/tex]

    The lcm: [tex] [175,35] = \prod_i p_i^{max(\alpha_i,\beta_i)}[/tex]

    [tex] [175,35] = 5^2\cdot7^1 = 175[/tex]

    So now I need to express the gcd as a linear combination. Is this correct:

    [tex]ax + by = d[/tex] where [tex]d = (a,b)[/tex]

    [tex]175x + 35y = 35[/tex]

    [tex]x = 0[/tex] and [tex]y = 1[/tex]

    [tex]\therefore 175\cdot(0) + 35\cdot(1) = 35[/tex]

    Hopefully I'm on the right track, although I can see there being multiple solutions for the linear combination.

    Thanks in advance for your help, comments, tips, clues, commentaries... :smile:
  2. jcsd
  3. Oct 27, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    That all looks correct.

    You might consider using Euclid's algoritm for finding the GCD - it dovetails nicely with the linear combination thing.
  4. Oct 27, 2004 #3
    Thanks for the reply.

    It looks like the Euclidean Algorith would result in a one liner:

    [tex]175 = 5\cdot35 + 0[/tex]

    How would you "pull" the linear combination out of that? I must be missing something simple.

    Thanks again.
  5. Oct 27, 2004 #4


    User Avatar
    Science Advisor
    Homework Helper

    Well, the example you gave is a special case b/c the gcf is one of the factors. If you had somehting like:

    Then you'd be able to use the Euclidean algoritm to find the LCF directly.

    [tex]20 - (35 - 20) = 5[/tex]
    readily leads to the the linear combination
    [tex]2 \times 20 - 1 \times 35 = 5[/tex]

    I guess, that mostly, I like Euclid's algorithm because it's less computationally complex - it takes roughly [tex]\log(n)[/tex] time while factoring can take [tex]n^{\frac{1}{4}}[/tex] or so time. I suppose it doesn't much matter unless you're dealing with big numbers.
  6. Oct 27, 2004 #5

    After reading your replies and vary info on the web (and in texts), it's very clear now.

    Thanks much!
  7. Oct 27, 2004 #6


    User Avatar
    Science Advisor
    Homework Helper

    Hi, I thought I'd point out that you can find the lcm without factoring also. You have the relation gcd(a,b)*lcm(a,b)=a*b, for any positive integers a, b. So you can use the euclidean algorithm to find the gcd, then the lcm follows with little effort.

    Also, when the euclidean algorithm spat out 175=(5)35+0, you knew the gcd was 35, since it divides both numbers. The obvious linear combination is the one you ended with, taking the coefficient of 35 to be 1. If you wanted more, you could rearrange the equation to get:




    Get as many different ones as you like by adding any integer multiple of (1)175-(5)35 to the left hand side.
    Last edited: Oct 27, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook