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
-
0@ 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. – 2012-03-21
-
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.