- #1

- 1,426

- 1

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Werg22
- Start date

- #1

- 1,426

- 1

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

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

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,440

- 138

I perfer a definition that does not require an ordering of element such asHurkyl said:

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)

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,950

- 19

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.

Share: