Is the gcd function symmetric?

  • Thread starter iamsmooth
  • Start date
  • #1
103
0
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.
 

Answers and Replies

  • #2
59
0
Yes. This is apparent from the definition of the words "greatest" and "common".
 
  • #3
62
0
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. -_-'''
 

Related Threads on Is the gcd function symmetric?

Replies
6
Views
1K
  • Last Post
Replies
2
Views
6K
Replies
1
Views
522
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
884
Replies
2
Views
4K
Top