Let p be a prime dividing a natural number n. Show that:

$\frac{n}{p}\equiv \binom{n}{p}\mod n$

Now this seems like it should follow from Lucas' theorem

Indeed as a corollary of Lucas theorem we have that:

$\frac{n}{p}\equiv \binom{n}{p}\mod p$

I was however unable to show that the desired result follows from this. I am interested in a proof that uses the above corollary, if one exists. (This problem is not homework).


$$\binom{n}{p} - \dfrac{n}{p} = \dfrac{n}{p}\Big(\binom{n-1}{p-1}-1\Big),$$ so it suffices to show that what's in the parenthesis is divisible $p$. Can you see how that follows from Lucas's theorem? Or you can brute force it giving common denominator.

  • $\begingroup$ Thank you, this is very clear. $\endgroup$ – qwert4321 Feb 28 '17 at 6:26

Let $n=kp$, $p\ge 3$, and let $i^{-1}$ denote the https://en.wikipedia.org/wiki/Modular_multiplicative_inverse $$\binom{n}{p}=\binom{kp}{p}=k\cdot\prod_{i=1}^{p-1}\frac{kp-i}{i}=k\cdot\prod_{i=1}^{p-1}(kp-i)i^{-1}\equiv k\cdot\prod_{i=1}^{p-1}(-i)i^{-1}=k(-1)^{p-1}=k=\frac{n}{p}$$ the congruence is $\pmod{n}$

  • $\begingroup$ This doesn't work if there is an i that is not invertible mod n. e.g. if k=3,p=5, then i=3 is not invertible mod 15. This argument however does show the corollary in the question if we do the reductions mod p. $\endgroup$ – qwert4321 Feb 28 '17 at 7:59

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.