- #1

- 1,425

- 1

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

- Thread starter Werg22
- Start date

- #1

- 1,425

- 1

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

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

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

- 135

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

- 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.

- Last Post

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 1K

- Replies
- 8

- Views
- 2K

- Replies
- 4

- Views
- 524