Skip to main content
deleted 1 characters in body
Source Link
tc1729
  • 3.2k
  • 1
  • 22
  • 42

Here's a slightly different proof from the one's presented above: We show that for a prime $p$ we can show that $p|\binom{p^k}{i}$ for $1\le i\le p^k-1$. Due to the fact that $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y+\rfloor$$\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor$ we have $$\sum_{j=1}^{k}\left(\left\lfloor\frac{i}{p^j}\right\rfloor+\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\le\sum_{j=1}^{k}\left\lfloor\frac{p^k}{p^j}\right\rfloor.$$ The LHS is the number of factors of $p$ in $i!(p^k-i)!$ and the RHS is the number of factors of $p$ in $p^k!$, by Legendre's formula. We have $$\left\lfloor\frac{i}{p^k}\right\rfloor=\left\lfloor\frac{p^k-i}{p^k}\right\rfloor = 0, \left\lfloor\frac{p^k}{p^k}\right\rfloor=1,$$ so the inequality is strict, so at least one factor of $p$ must divide $\binom{p^k}{i}$.

Here's a slightly different proof from the one's presented above: We show that for a prime $p$ we can show that $p|\binom{p^k}{i}$ for $1\le i\le p^k-1$. Due to the fact that $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y+\rfloor$ we have $$\sum_{j=1}^{k}\left(\left\lfloor\frac{i}{p^j}\right\rfloor+\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\le\sum_{j=1}^{k}\left\lfloor\frac{p^k}{p^j}\right\rfloor.$$ The LHS is the number of factors of $p$ in $i!(p^k-i)!$ and the RHS is the number of factors of $p$ in $p^k!$, by Legendre's formula. We have $$\left\lfloor\frac{i}{p^k}\right\rfloor=\left\lfloor\frac{p^k-i}{p^k}\right\rfloor = 0, \left\lfloor\frac{p^k}{p^k}\right\rfloor=1,$$ so the inequality is strict, so at least one factor of $p$ must divide $\binom{p^k}{i}$.

Here's a slightly different proof from the one's presented above: We show that for a prime $p$ we can show that $p|\binom{p^k}{i}$ for $1\le i\le p^k-1$. Due to the fact that $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor$ we have $$\sum_{j=1}^{k}\left(\left\lfloor\frac{i}{p^j}\right\rfloor+\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\le\sum_{j=1}^{k}\left\lfloor\frac{p^k}{p^j}\right\rfloor.$$ The LHS is the number of factors of $p$ in $i!(p^k-i)!$ and the RHS is the number of factors of $p$ in $p^k!$, by Legendre's formula. We have $$\left\lfloor\frac{i}{p^k}\right\rfloor=\left\lfloor\frac{p^k-i}{p^k}\right\rfloor = 0, \left\lfloor\frac{p^k}{p^k}\right\rfloor=1,$$ so the inequality is strict, so at least one factor of $p$ must divide $\binom{p^k}{i}$.

Source Link
tc1729
  • 3.2k
  • 1
  • 22
  • 42

Here's a slightly different proof from the one's presented above: We show that for a prime $p$ we can show that $p|\binom{p^k}{i}$ for $1\le i\le p^k-1$. Due to the fact that $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y+\rfloor$ we have $$\sum_{j=1}^{k}\left(\left\lfloor\frac{i}{p^j}\right\rfloor+\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\le\sum_{j=1}^{k}\left\lfloor\frac{p^k}{p^j}\right\rfloor.$$ The LHS is the number of factors of $p$ in $i!(p^k-i)!$ and the RHS is the number of factors of $p$ in $p^k!$, by Legendre's formula. We have $$\left\lfloor\frac{i}{p^k}\right\rfloor=\left\lfloor\frac{p^k-i}{p^k}\right\rfloor = 0, \left\lfloor\frac{p^k}{p^k}\right\rfloor=1,$$ so the inequality is strict, so at least one factor of $p$ must divide $\binom{p^k}{i}$.