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

What is gcd?

  1. Sep 24, 2005 #1
    What does the notation gcd(x,y) means?
  2. jcsd
  3. Sep 24, 2005 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It stands for greatest common divisor. It has two equivalent characterizations:

    d = gcd(x, y) iff d is the largest thing such that d|x and d|y.

    d = gcd(x, y) iff d is the smallest nonzero thing of the form ux + vy. (u and v need not be greater than zero)

    (Size is measured by absolute value. We always use the positive one)

    Note that all of this makes sense for more than just integers -- for example, it works for polynomials if "size" is measured by degree. (We always choose the monic polynomial)
  4. Sep 24, 2005 #3


    User Avatar
    Homework Helper

    I perfer a definition that does not require an ordering of element such as

    gcd(x,y)=d iff d|x,y and if c|x,y then c|d
    That is to say d is a common divisor of x and y
    all common divisors of x and y divide d
  5. Sep 24, 2005 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, to be entirely silly, | is a (pre)ordering. :smile: (An actual partial ordering on things like the positive integers, or monic polynomials!)

    I feel that the characterization as the least nonzero linear combination to be a generally more useful characterization, but I guess that gets translated in the same way: d = ux + vy, and d | ax + by for all a and b.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: What is gcd?
  1. What is ^? (Replies: 2)

  2. GCD of polynomials? (Replies: 4)

  3. Gcd(a,b) = gcd(a,b+a) (Replies: 4)