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

  • $\begingroup$ @ 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. $\endgroup$ – Andylang Mar 21 '12 at 4:20
  • $\begingroup$ Actually, the assertion in the question need not follow if $a_1=a_2=\cdots = a_n>1$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.