• Support PF! Buy your school textbooks, materials and every day products Here!

Does the GCD of a set divide the GCD of any subset?

  • Thread starter jack476
  • Start date
  • #1
314
122

Homework Statement


If A is a set of integers and B is a set properly contained in A, does the greatest common denominator of all of the integers in A divide the greatest common denominator of all elements in B?

Homework Equations


None.

The Attempt at a Solution


Obviously gcd(A) divides any element of B, since anything in B is contained is also in A, but I can't get from there to anything about the relationship between gcd(A) and gcd(B).
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
It's not the most elegant way, but it's quick and easy: try proof by contradiction.
Let ##a=gcd(A)## so that ##\forall x\in A:\ a|x##
and
##b=gcd(B)## so that ##\forall x\in B:\ b|x##

Assume that ##a\nmid b##. By looking at prime power divisors of ##a## that are not divisors of ##b## you should be able to find a way of making a common divisor of ##B## that is bigger than ##b##, thereby contradicting the supposition that ##b## is a GCD of ##B##.
 

Related Threads for: Does the GCD of a set divide the GCD of any subset?

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
5K
Replies
1
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
1K
Top