0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you think about it? $\endgroup$ – user228113 Nov 20 '15 at 21:50
  • $\begingroup$ 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. $\endgroup$ – user19405892 Nov 20 '15 at 21:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Barry Cipra Nov 20 '15 at 21:55
  • $\begingroup$ 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. $\endgroup$ – user19405892 Nov 20 '15 at 22:00
  • 1
    $\begingroup$ @user1196158, if you do what I suggested in my previous comment, you should quickly convince yourself that the answer is not $p^n$. $\endgroup$ – Barry Cipra Nov 20 '15 at 22:02
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why can't the GCD be $1$? $\endgroup$ – user19405892 Nov 20 '15 at 22:12
  • $\begingroup$ You could try to count prime factors $p$ in a general term $\binom{p^n}{i}$, similar to what I did above. $\endgroup$ – user133281 Nov 20 '15 at 22:14
  • $\begingroup$ Don't you mean that the numerator contains $1$ more factor of $p$ than the denominator? $\endgroup$ – user19405892 Nov 20 '15 at 22:23
  • $\begingroup$ Yes (because it contains one more when $i=0$). $\endgroup$ – user133281 Nov 20 '15 at 22:27
  • $\begingroup$ We get $\displaystyle \prod_{m=0}^{i-1} \frac{p^n-m}{i-m}$ for $\displaystyle \binom{p^n}{i}$. Then what? $\endgroup$ – user19405892 Nov 20 '15 at 22:34

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.