1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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)