Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What have you tried? – user5137 Mar 20 '12 at 17:24
@ 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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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