Primes and the Binomial Theorem

Primes and the Binomial Theorem

Let $p$ be a prime. Then for $1\le k\le p-1$:

$$\begin{array}{rl}& a)p\mid (\genfrac{}{}{0ex}{}{p}{k})\\ & b)(a+b{)}^p\equiv a^p+b^p(\mathrm{mod}p)\end{array}$$

Proof a) By definition,

$$\left(\genfrac{}{}{0ex}{}{p}{k}\right)=\frac{p!}{k!(p-k)!}=\frac{p\cdot (p-1)\cdots (p-k+1)}{k!}$$

Since $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ is an integer, and $k!$ cannot divide p, $k!$ must divide $(p-1)\cdots (p-k+1)$. Call this part $\ell$. Then we can rewrite $\left(\genfrac{}{}{0ex}{}{p}{k}\right)=p\cdot \ell$, which is $p\mid \left(\genfrac{}{}{0ex}{}{p}{k}\right)$.

b) By the binomial theorem, we can use part a) to cancel terms in the following way:

$$\begin{array}{rl}(a+b{)}^p& =\left(\genfrac{}{}{0ex}{}{p}{0}\right)a^p+\left(\genfrac{}{}{0ex}{}{p}{1}\right)a^{p-1}b+\cdots +\left(\genfrac{}{}{0ex}{}{p}{p-1}\right)a{b}^{p-1}+\left(\genfrac{}{}{0ex}{}{p}{p}\right)b^p\\ & \equiv \left(\genfrac{}{}{0ex}{}{p}{0}\right)a^p+0+\cdots +0+\left(\genfrac{}{}{0ex}{}{p}{p}\right)b^p\\ & \equiv a^p+b^p(\mathrm{mod}p).\end{array}$$