Wilson定理和Lucas定理

Wilson定理

对于自然数$n>1$,当且仅当$n$是素数时,$(n-1)! \equiv -1\pmod{n}$.

证明：先证对素数$p$有$(p-1)!\equiv -1 \pmod{p}$.
$p=2,3$时显然，当$p>3$时，$\mathbb{F}_{p}:=\mathbb{Z}/p\mathbb{Z}$为域，非零元皆有乘法逆元.
考虑$a^{2}\equiv 1\pmod{p} \Rightarrow 0 \equiv a^{2}-1\equiv(a+1)(a-1) \pmod{p}\Rightarrow a=1,p-1$
故$\mathbb{F}_{p} \smallsetminus \{0,1,p-1\}$中所有元素乘积为$1$，进而有$\mathbb{F}_{p}$中所有非零元素之积为$-1$

另一方面，当$n$为合数时，假设$(n-1)!\equiv -1 \pmod{n}$，即存在整数$k$使得$(n-1)\neq kn-1$成立。因为$n$是合数，必然存在素数$p<n$使得$n=pm$，所以$(n-1)! =kpm-1\equiv -1 \pmod{p}$。但乘积$(n-1)!$中必然已出现过$p$，故而一定有$(n-1)!\equiv 0 \pmod{p}$，矛盾。

---

Lucas定理

对于素数$p$,有$\dbinom{n}{k}\equiv \dbinom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{k}{p} \right\rfloor}\dbinom{n \bmod p}{k \bmod p} \pmod{p}$
其中,当$n<k$时,二项式系数$\tbinom{n}{k}$规定为$0$.

证明：考虑$\tbinom{p}{n} \bmod p$的取值，$\tbinom{p}{n}=\frac{p!}{n!(p-n)!}$.当$n\neq0,p$时，分母中没有因子$p$，但分子中有因子$p$，且二项式系数为整数，故必为$p$的倍数；而当$n=0,p$时$\tbinom{p}{n}= 1$，于是

$$\dbinom{p}{n} = \begin{cases} 0, & n \neq 0,p \\ 1, & n= 0,p \end{cases} \pmod p$$

则有

$$(x+y)^{p}\equiv x^{p} + y^{p} \pmod{p}.$$

接下来有

$$\begin{align} (1+x)^{n} & =(1+x)^{p\lfloor n/p \rfloor }(1+x )^{n \bmod p} \\ & \equiv (1+x^{p})^{\lfloor n/p \rfloor }(1+x)^{n \bmod p} \pmod{p}. \end{align}$$

考虑两侧的$x^{k}$系数
$LHS=\dbinom{n}{k} \bmod p.$对于右侧，对$k$作唯一的带余除法$k= p\left\lfloor \frac{k}{p} \right\rfloor+(k \bmod p)$，因此，$RHS=\dbinom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{k}{p} \right\rfloor}\dbinom{n \bmod p}{k \bmod p} \bmod p.$得证.

推论:设$n,m \in \mathbb{Z}_{\geq 1}$有$p$进制展开$n=\sum_{k\geq 0}a_{k}p^{k},m=\sum_{k\geq 0}b_{k}p^{k}$,则

$$\dbinom{n}{m}\equiv \prod_{k\geq 0} \dbinom{a_{k}}{b_{k}} \pmod{p}.$$

此即不断应用$Lucas$定理展开尽的结果，这里另外给出一个证明。

证：由$(x+y)^{p}=x^{p}+y^{p} \pmod{p}.$在多项式环$\mathbb{F}_{p}[x]$中有

$$(x+1)^{n}=\prod_{k\geq 0}(x^{p^{k}}+1)^{a_{k}}=\prod_{k\geq 0}\left( \sum_{h_{k}=0}^{p-1} \dbinom{a_{k}}{h_{k}}x^{h_{k}p^{k}} \right)$$

观察两侧$x^{m}$的系数，再由$p$进制展开的唯一性即得证.