What is gcd?

  • Thread starter Werg22
  • Start date
  • #1
1,425
1

Main Question or Discussion Point

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

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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)
 
  • #3
lurflurf
Homework Helper
2,423
123
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
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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.
 

Related Threads for: What is gcd?

  • Last Post
Replies
4
Views
952
  • Last Post
Replies
4
Views
2K
Replies
3
Views
1K
Replies
8
Views
2K
Replies
4
Views
450
Top