# Greatest Common Divisor of Several Integers

Let $N=\{a_1,a_2,...,a_n\}$ be a set of integers each $\ge$ $1$. Let $P(k)$ be the product of the ${n\choose k}$ LCMs of all the $k$-blocks of $N$ (subsets of $N$ with $k$ elements). Problem: Show that the GCD of $N$ equals $$\frac{P(1)P(3)P(5)\cdots}{P(2)P(4)P(6)\cdots}.$$

• @ Jack Maney:I have tried induction on $n$ but failed.And I observes the situations when n=3,4 so that I hope I can find out the law.But I still don't know how to do. – Andylang Mar 21 '12 at 4:20
• Actually, the assertion in the question need not follow if $a_1=a_2=\cdots = a_n>1$. – user5137 Mar 21 '12 at 4:34

Suppose for the moment that $p$ is some prime and that $\{a_1,\dots,a_n\} = \{p^{b_1},\dots,p^{b_n}\}$. Then the GCD of $\{a_1,\dots,a_n\}$ is just $p^{\min\{b_1,\dots,b_n\}}$, while the LCM of any $k$-block is just $p$ to the maximum of the $b_j$ occurring in that block. Therefore in this special case, the problem is equivalent to the following:
Let $M = \{b_1,\dots,b_n\}$ be a set of nonnegative integers. Let $Q(k)$ be the sum of the $\binom nk$ maximums of all the $k$-blocks of $M$. Show that the minimum of $M$ equals $$Q(1) - Q(2) + Q(3) - Q(4) + Q(5) - Q(6) + \cdots.$$ This is not too hard to prove (note that reordering the elements doesn't matter, so without loss of generality $b_1 \le b_2\le \cdots\le b_n$).
The reason this special case is worth mentioning is that your original problem can be proved one prime at a time. In other words, you can prove that the GCD of $N$ equals the product/quotient of the $P(k)$ by showing that, for every prime $p$, the power of $p$ dividing the GCD equals the power of $p$ dividing the product/quotient.