Lucas's theorem
Statement:
\[C_{a}^{b}\equiv C_{\lfloor a/p\rfloor}^{\lfloor b/p\rfloor}\cdot C_{a\mod p}^{b\mod p}\pmod p\]where $p$ is a prime and $a,b$ are both non-negative integers.
Proof:
It’s obvious that $p \mid C_{p}^{n}(n=1,2,\ldots, n-1)$ for every prime p, so we have
\[(1+x)^p\equiv 1+x^p\pmod p\]Knowing these, we can write $a$ and $b$ in Euclidean division form:
\[\begin{cases} a=pq_{a}+r_{a}\\ b=pq_{b}+r_{b} \end{cases}\]Now pay attention to the following formula:
\[\begin{align*} (1+x)^a&=(1+x)^{pq_{a}+r_{a}}\\ &=[(1+x)^p]^{q_{a}}\cdot (1+x)^{r_a}\\ &\equiv (1+x^p)^{q_a}\cdot (1+x)^{r_a}\pmod p \end{align*}\]Note that the coeffient of $x^{b}$ in the left part is $C_{a}^{b}$. Then we turn to the right part, because every $x$’s exponent is $kp+r$ where $k$ and $r(0 \leq r<p)$ are all non-negtive integers. According to Euclidean division, what makes the exponent of $x$ to $b$ is $pq_{b}+r_{b}$ and in this situation the coeffient is
\[C_{\lfloor a/p\rfloor}^{\lfloor b/p\rfloor}\cdot C_{a\mod p}^{b\mod p}\]QED.
If we keep using iteration, what we’ll get is:
\[\begin{align*} C_{a}^{b}&\equiv C_{\lfloor a/p\rfloor}^{\lfloor b/p\rfloor}\cdot C_{a\mod p}^{b\mod p}\pmod p\\ &\equiv C_{\lfloor a'/p\rfloor}^{\lfloor b'/p\rfloor}\cdot C_{a'\mod p}^{b'\mod p}\cdot C_{a\mod p}^{b\mod p}\pmod p\\&where\quad b'=\lfloor b/p\rfloor,a'=\lfloor a/p\rfloor\\ &\ldots\\ &\equiv C_{a_0}^{b_0}\cdot C_{a_1}^{b_1}\cdot\ldots\cdot C_{a_d}^{b_d}\pmod p \end{align*}\]where
\[a=a_0+a_1p+\ldots+a_dp^d,\\ b=b_0+b_1p+\ldots+b_dp^d\]this is another form of Lucas’s theorem.
Corollary:
\[C_{n}^{p}\equiv \lfloor n/p\rfloor \pmod p\]Further more, using Lucas’s theorem smartly, we can get Fine’s Theorem:
there are $\prod_{i=0}^{d}(1+n_i)$ numbers in set ${C_{n}^{k}(k=0,1,2\ldots,n)}$ which can’t be divided by $p$. where $n=n_0+n_1p+\ldots+n_dp^d$. the proof is pretty easy cause every $C_{n_i}^{k_i}(i=0,1,2,\ldots,d)$ should not be $0$ if $p\nmid C_{n}^{k}$, $k_i$ is not greater than $n_i$.
Using Fine’s theorem, we know there are $2^{popcount(l-1)}$ odd numbers in the $l$th line of Pascal triangle , where $popcount(x)$ means the number of $1$ in the binary format of $x$.