# GCD of binomial coefficients of the form ($p^n$ choose $k$)

Let $n$ be a positive integer and $p$ be a prime. Find the greatest common factor of $\binom{p^n}{1}, \binom{p^n}{2},...,\binom{p^n}{p^n-1}$.

Progress: We know that for any given $n$ and $k$ in $\binom{p^n}{k}$, $$\sum_{m = 1}^\infty \biggl \lfloor \dfrac{p^n}{p^m} \biggr \rfloor \geq \sum_{m=1}^\infty \biggl [\biggl \lfloor \dfrac{p^n-k}{p^m} \biggr \rfloor + \biggl \lfloor \dfrac{n}{p^m} \biggr \rfloor \biggr]$$ because of the inequality $\displaystyle \lfloor x+y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor$. But this doesn't prove that each combination has to be divisible by $p^n$ because some may have no factors of $p$. So I am stuck here.

• What do you think about it? – user228113 Nov 20 '15 at 21:50
• We know that for any given $n$ and $k$ in $\binom{p^n}{k}$, $\displaystyle \sum_{m = 1}^\infty \biggl \lfloor \dfrac{p^n}{p^m} \biggr \rfloor \geq \sum_{m=1}^\infty \biggl [\biggl \lfloor \dfrac{p^n-k}{p^m} \biggr \rfloor + \biggl \lfloor \dfrac{n}{p^m} \biggr \rfloor \biggr]$ because of the inequality $\displaystyle \lfloor x+y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor$. But this doesn't prove that each combination has to be divisible by $p^n$ because some may have no factors of $p$. So I am stuck here. – user19405892 Nov 20 '15 at 21:50
• When faced with a problem like this, especially if you get stuck, you should always always always compute a bunch of examples. In this case, write down a chunk of Pascal's triangle until you run out of room and look at the rows that correspond to prime powers, like $4$, $8$, and $9$, and see if anything stands out. – Barry Cipra Nov 20 '15 at 21:55
• It seems like the answer is $p^n$, but I am not sure how to prove it. Edit: Oh, wait. For $p^n = 9$ it doesn't hold. – user19405892 Nov 20 '15 at 22:00
• @user1196158, if you do what I suggested in my previous comment, you should quickly convince yourself that the answer is not $p^n$. – Barry Cipra Nov 20 '15 at 22:02

Hint: Consider $$\binom{p^n}{p^{n-1}} = \frac{p^n(p^n-1) \cdots (p^n-p^{n-1}+1)}{p^{n-1} (p^{n-1}-1) \cdots 2 \cdot 1} = \prod_{i=0}^{p^{n-1}-1} \frac{p^n-i}{p^{n-1}-i}.$$ For each $i > 0$, the denominator and numerator of the rightmost fraction contain the same amount of prime factors $p$ (namely the same amount as $i$ has). It follows that $\binom{p^n}{p^{n-1}}$ contains only one prime factor $p$. Since $\binom{p^n}{1} = p^n$, this means that the GCD is either $1$ or $p$. Can you exclude the first possibility?
• Why can't the GCD be $1$? – user19405892 Nov 20 '15 at 22:12
• You could try to count prime factors $p$ in a general term $\binom{p^n}{i}$, similar to what I did above. – user133281 Nov 20 '15 at 22:14
• Don't you mean that the numerator contains $1$ more factor of $p$ than the denominator? – user19405892 Nov 20 '15 at 22:23
• Yes (because it contains one more when $i=0$). – user133281 Nov 20 '15 at 22:27
• We get $\displaystyle \prod_{m=0}^{i-1} \frac{p^n-m}{i-m}$ for $\displaystyle \binom{p^n}{i}$. Then what? – user19405892 Nov 20 '15 at 22:34