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$
8
  • $\begingroup$ What do you think about it? $\endgroup$
    – user228113
    Nov 20, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 22:02

1 Answer 1

Reset to default
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$
5
  • $\begingroup$ Why can't the GCD be $1$? $\endgroup$
    – user19405892
    Nov 20, 2015 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, 2015 at 22:14
  • $\begingroup$ Don't you mean that the numerator contains $1$ more factor of $p$ than the denominator? $\endgroup$
    – user19405892
    Nov 20, 2015 at 22:23
  • $\begingroup$ Yes (because it contains one more when $i=0$). $\endgroup$
    – user133281
    Nov 20, 2015 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, 2015 at 22:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .