1. Not finding help here? Sign up for a free 30min 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!

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

  1. May 18, 2016 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations
    None.

    3. 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).
     
  2. jcsd
  3. May 18, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Does the GCD of a set divide the GCD of any subset?
  1. Set theory, gcd (Replies: 2)

  2. GCD and LCD (Replies: 0)

Loading...