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

1. May 18, 2016

### jack476

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. May 18, 2016

### andrewkirk

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