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

460 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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?