Mod 相关

Lucas 定理

对质数 p 有

$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\mathrm{mod}p=\left(\genfrac{}{}{0ex}{}{\lfloor n/p\rfloor }{\lfloor m/p\rfloor }\right)\left(\genfrac{}{}{0ex}{}{n\mathrm{mod}p}{m\mathrm{mod}p}\right)\mathrm{mod}p.$$

推论：

• $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ 为奇数当且仅当 $n\&m=m$

Wilson 定理

$$(p-1)!\mathrm{mod}p=\{\begin{array}{ll}-1,& p\in \mathbb{P}\\ 2,& p=4\\ 0,& \text{otherwise}\end{array}.$$