I have this conjecture. can you please give me a proof? I could not find proof.

Question

$$ \left(\begin{array}{c}p\\ k\end{array}\right)\equiv\frac{p}{k}\bmod p $$ where p is composite number and k is one of its prime factor.

Answer 1

We have $$\binom{n-1}{p-1} = \frac{(n-1) \dotsb (n-p+1)}{(p-1)!}$$

Modulo $p$ the numerator is also $(p-1)!$, thus the quotient is $1$ modulo $p$, i.e. $\binom{n-1}{p-1}=1+ap$ for some $a \in \mathbb Z$.

This yields $$\binom{n}{p}=\frac{n}{p}\binom{n-1}{p-1}=\frac{n}{p}(1+ap)=\frac{n}{p}+an = \frac{n}{p} \mod n.$$