Homework Help: Is the gcd function symmetric?

1. Apr 27, 2010

iamsmooth

Just a quick theory question. I'd assume it is, but usually the bigger number goes first.

e.g. gcd(10, 5) = 2

but does gcd (5, 10) = 2?

My guess is yes.

Thanks for the help.

2. Apr 27, 2010

Gigasoft

Yes. This is apparent from the definition of the words "greatest" and "common".

3. Apr 28, 2010

Legendre

My input is probably trivial but I thought it would be nice to prove it formally.

We need : gcd(x,y) = gcd(y,x)

Suppose gcd(x,y) = d. Then x = nd and y = md for some integers n,m where gcd(n,m) = 1.

So gcd(y,x) = gcd (md,nd) = d because gcd(m,n) =1.

We have shown for all x,y that gcd(x,y) = gcd(y,x).

P.S.
Hopefully no silly errors. -_-'''