TAOCP 1.2.6 Exercise 10
Let n=ap+b,\qquad 0\le b<p, where $a=\lfloor n/p\rfloor$ and $b=n\bmod p$.
Section 1.2.6: Binomial Coefficients
Exercise 10. [M25] If $p$ is prime, show that:
- $\binom{n}{p} \equiv \lfloor n/p \rfloor \pmod p$.
- $\binom{p}{k} \equiv 0 \pmod p$, for $1 \le k \le p-1$.
- $\binom{p-1}{k} \equiv (-1)^k \pmod p$, for $0 \le k \le p-1$.
- $\binom{p+1}{k} \equiv 0 \pmod p$, for $2 \le k \le p-1$.
- (E. Lucas, 1877.)
$$ \binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \binom{n \bmod p}{k \bmod p} \pmod p. $$
- If the $p$-ary number system representations of $n$ and $k$ are
$$ n = a_rp^r + \cdots + a_1p + a_0,\qquad k = b_rp^r + \cdots + b_1p + b_0, $$
then
$$ \binom{n}{k} \equiv \binom{a_r}{b_r}\cdots\binom{a_1}{b_1}\binom{a_0}{b_0} \pmod p. $$
Verified: yes
Solve time: 47s
Solution
Let
$$ n=ap+b,\qquad 0\le b<p, $$
where $a=\lfloor n/p\rfloor$ and $b=n\bmod p$.
By Eq. (5),
$$ \binom{n}{p} =\frac{n(n-1)\cdots(n-p+1)}{p!} =\frac{n(n-1)\cdots(n-p+1)}{p(p-1)!}. $$
Since $p$ is prime, none of the integers $1,2,\ldots,p-1$ is divisible by $p$. Hence $(p-1)!$ is invertible modulo $p$.
Among the $p$ consecutive integers
$$ n,n-1,\ldots,n-p+1, $$
exactly one is divisible by $p$, namely $ap$. Therefore
$$ \binom{n}{p} =\frac{ap}{p}\cdot \frac{(ap+b)(ap+b-1)\cdots(ap+b-p+1)}{ap,(p-1)!}. $$
Modulo $p$, the numerator of the second factor becomes
$$ b(b-1)\cdots1(-1)(-2)\cdots(-(p-1-b)). $$
Hence
$$ \frac{(ap+b)\cdots(ap+b-p+1)}{ap} \equiv b!,(-1)^{p-1-b}(p-1-b)! \pmod p. $$
Therefore
$$ \binom{n}{p} \equiv a\cdot \frac{b!,(-1)^{p-1-b}(p-1-b)!}{(p-1)!} \pmod p. $$
Since
$$ (p-1)! = (p-1)(p-2)\cdots(b+1)b! \equiv (-1)(-2)\cdots(-(p-1-b))b! $$
$$= (-1)^{p-1-b}(p-1-b)!b! \pmod p,$$
the quotient is congruent to $1$. Thus
$$ \binom{n}{p}\equiv a\equiv\lfloor n/p\rfloor\pmod p. $$
Hence
$$ \boxed{\binom{n}{p}\equiv\lfloor n/p\rfloor\pmod p.} $$
For part 2, Eq. (5) gives
$$ \binom{p}{k} = \frac{p!}{k!(p-k)!}, \qquad 1\le k\le p-1. $$
The numerator contains a factor $p$, while neither denominator factor is divisible by $p$. Hence
$$ \binom{p}{k}\equiv0\pmod p, \qquad 1\le k\le p-1. $$
Therefore
$$ \boxed{\binom{p}{k}\equiv0\pmod p,\qquad 1\le k\le p-1.} $$
For part 3, Eq. (7) yields
$$ \binom{p-1}{k} = \frac{p-1}{k}\binom{p-2}{k-1}. $$
Reducing modulo $p$,
$$ \binom{p-1}{k} \equiv -\frac1k\binom{p-2}{k-1}\pmod p. $$
Applying Eq. (7) repeatedly,
$$ \binom{p-1}{k} = \frac{(p-1)(p-2)\cdots(p-k)}{k!} \equiv \frac{(-1)(-2)\cdots(-k)}{k!} = (-1)^k \pmod p. $$
Hence
$$ \boxed{\binom{p-1}{k}\equiv(-1)^k\pmod p,\qquad 0\le k\le p-1.} $$
For part 4, Eq. (5) gives
$$ \binom{p+1}{k} = \frac{(p+1)p(p-1)\cdots(p-k+2)}{k!}, \qquad 2\le k\le p-1. $$
The numerator contains the factor $p$, while $k!$ is not divisible by $p$. Therefore
$$ \binom{p+1}{k}\equiv0\pmod p, \qquad 2\le k\le p-1. $$
Thus
$$ \boxed{\binom{p+1}{k}\equiv0\pmod p,\qquad 2\le k\le p-1.} $$
For part 5, write
$$ n=ap+b,\qquad k=cp+d, $$
where
$$ 0\le b,d<p. $$
By the binomial theorem (13),
$$ (1+x)^p = \sum_{j=0}^p\binom{p}{j}x^j. $$
By part 2,
$$ (1+x)^p\equiv1+x^p\pmod p. $$
Hence
$$ (1+x)^n = \bigl((1+x)^p\bigr)^a(1+x)^b \equiv (1+x^p)^a(1+x)^b \pmod p. $$
Expanding again by Eq. (13),
$$ (1+x^p)^a(1+x)^b = \left(\sum_{i=0}^a\binom ai x^{pi}\right) \left(\sum_{j=0}^b\binom bj x^j\right). $$
The coefficient of $x^{cp+d}$ is therefore
$$ \binom ac\binom bd. $$
Since the coefficient of $x^k$ in $(1+x)^n$ is $\binom nk$, we obtain
$$ \binom nk \equiv \binom ac\binom bd \pmod p. $$
Substituting
$$ a=\lfloor n/p\rfloor,\qquad c=\lfloor k/p\rfloor,\qquad b=n\bmod p,\qquad d=k\bmod p, $$
gives
$$ \boxed{ \binom{n}{k} \equiv \binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor} \binom{n\bmod p}{k\bmod p} \pmod p. } $$
For part 6, apply part 5 repeatedly. Write
$$ n=a_rp^r+\cdots+a_1p+a_0, \qquad k=b_rp^r+\cdots+b_1p+b_0. $$
Then
$$ \left\lfloor\frac np\right\rfloor = a_rp^{r-1}+\cdots+a_1, \qquad n\bmod p=a_0, $$
and similarly for $k$. Therefore part 5 gives
$$ \binom nk \equiv \binom{a_rp^{r-1}+\cdots+a_1} {b_rp^{r-1}+\cdots+b_1} \binom{a_0}{b_0} \pmod p. $$
Applying the same argument to the first binomial coefficient,
$$ \binom{a_rp^{r-1}+\cdots+a_1} {b_rp^{r-1}+\cdots+b_1} \equiv \binom{a_rp^{r-2}+\cdots+a_2} {b_rp^{r-2}+\cdots+b_2} \binom{a_1}{b_1} \pmod p. $$
Continuing in this manner yields
$$ \binom nk \equiv \binom{a_r}{b_r}\cdots \binom{a_1}{b_1} \binom{a_0}{b_0} \pmod p. $$
Hence
$$ \boxed{ \binom{n}{k} \equiv \binom{a_r}{b_r}\cdots \binom{a_1}{b_1} \binom{a_0}{b_0} \pmod p. } $$
This completes the proof.
∎