# Show that $\frac{n}{p}\equiv \binom{n}{p}\mod n$

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).

## 2 Answers

$$\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.

• Thank you, this is very clear. – 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}$

• 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. – qwert4321 Feb 28 '17 at 7:59