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}.$
Greatest Common Divisor of Several Integers
-
0Actually, the assertion in the question need not follow if a_1=a_2=\cdots = a_n>1. – 2012-03-21
1 Answers
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.