# What is gcd?

Werg22
What does the notation gcd(x,y) means?

Staff Emeritus
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)

Homework Helper
Hurkyl said:
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)
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
and
all common divisors of x and y divide d

Staff Emeritus