2
$\begingroup$

In a question, it was asked to prove that if $p$ is an odd prime, $n>0$ and $0, and $\gcd(k,p)=1$, then

$${p^n\choose k}\equiv 0 \pmod {p^n}$$

My question is, is the hypothesis $p$ is an odd prime necessary? I have worked out a proof, but without using the fact that $p$ is odd, ie., my proof seems to work perfectly for $p=2$.

Sincere thanks for help.

  • 6
    Why don't you show your proof?2012-08-31
  • 5
    @draks, how about $\binom{p^n}{k} = \frac{p^n}{k} \binom{p^n-1}{k-1} \equiv p^n \cdot k^{-1} \binom{p^n-1}{k-1} \equiv 0 \pmod{p^n}$, which works as $k$ is invertible $\pmod{p^n}$.2012-08-31
  • 0
    @KarolisJuodelė Thanks! That is essentially how I proved it. $(k,p)=1 \Rightarrow (k,p^n)=1$ so by Euclid's lemma, $p^n \mid k {p^n \choose k}$ and $(k,p^n)=1$ implies $p^n \mid {p^n \choose k}$2012-08-31
  • 0
    @KarolisJuodelė: why not post that as an answer?2012-08-31
  • 0
    @KarolisJuodelė What is meant by $k$ is invertible $\pmod{p^n}$?Can you explain the last step?2012-08-31
  • 0
    @JavaMan, I didn't write anything OP didn't already know.2012-08-31
  • 0
    @SaurabhHota, $k$ being invertible $\pmod {n}$ means that there is some number $k^{-1}$ such that $k \cdot k^{-1} \equiv 1 \pmod {n}$. This is implied by $\gcd(k, n) = 1$. To see this, consider the values of $mk \pmod {n}$ for all $m \in \mathbb{N}$ and notice how large the cycle is.2012-08-31
  • 0
    @KarolisJuodelė Thank you for the explanation. But I still didn't understand how $\frac{7}{3} \equiv 7\cdot2 \pmod 5$ the similar thing you did in the second step.2012-08-31
  • 0
    @SaurabhHota, I suppose this makes more sense when talking about finite rings rather than remainders. The thing is that division $\pmod{n}$ is not the division you are thinking of. Though it's still the inverse of multiplication and can be used as such.2012-08-31
  • 0
    @KarolisJuodelė: I'm aware that you didn't write anything OP didn't know, but now it looks like the question has not been answered. Plus, why not copy your comments into an answer and then get credit for your response? (see http://meta.math.stackexchange.com/questions/1559/dealing-with-answers-in-comments for more).2012-08-31

1 Answers 1

2

The statement does indeed hold for $2$ as well as any other prime. Both proofs given in comments are correct and don't depend on $p$ being odd.