Gcd(a, b, c) = gcd(gcd(a,b), c)

  • Thread starter ashwinb
  • Start date
  • #1
1
0
Help please!
I basically have to prove that gcd(a, b, c) = gcd(gcd(a,b), c).
So I know that if I just need to prove that the sets {a, b, c} and {gcd(a,b), c} have the same sets of divisors.
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
welcome to pf!

hi ashwinb! welcome to pf! :wink:
gcd(a, b, c) = gcd(gcd(a,b), c)

you usually do this sort of thing by proving separately:
i] gcd(a, b, c) ≤ gcd(gcd(a,b), c)
ii] gcd(a, b, c) ≥ gcd(gcd(a,b), c)

how far have you got? :smile:
 
  • #3
150
0
A straightforward way of proving this is to use the prime factorizations of a, b, and c, that is, write a=∏ipαi, b=∏ipβi, and c=∏ipγi. Then gcd(a,b,c)=∏ipmin(αiii). Likewise, gcd(gcd(a,b),c)=∏ipmin(min(αii),γi). These are equal since min(αiii)=min(min(αii),γi).
 

Related Threads on Gcd(a, b, c) = gcd(gcd(a,b), c)

  • Last Post
Replies
4
Views
2K
Replies
0
Views
6K
  • Last Post
Replies
3
Views
8K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
3
Views
16K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
1K
Top