1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    Hopefully no silly errors. -_-'''
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook