Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Is the gcd function symmetric?

  1. Apr 27, 2010 #1
    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. jcsd
  3. Apr 27, 2010 #2
    Yes. This is apparent from the definition of the words "greatest" and "common".
     
  4. Apr 28, 2010 #3
    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. -_-'''
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook