已知 $p\text{ is prime},\gcd(a,p)=1$ 证明 $a^p\equiv a\pmod p$。

考虑一个引理：若 $p$ 是质数，$p\mid\dbinom{p}{i},\forall i\in[1,p-1],i\in \mathbb Z$。

$$
\because \dbinom{p}{i}=\dfrac{p!}{i!(p-i)!}\newline
又\because p \text{ is prime}\newline
\therefore (p-1)!\mid i!(p-i)!\newline
\therefore \dbinom{p}{i}=p\cdot\dfrac{(p-1)!}{i!(p-i)!}
$$

引理证毕。

通过这个引理我们能进一步得到一个结论：

$$
p\mid \sum\limits_{i=1}^{i<p} \dbinom{p}{i}\newline
$$

这个小结论等会儿会用。

回归原命题，容易发现 $a=1$ 时结论成立。

当 $a=2$ 时

$$
\begin{aligned}
a^p
&=2^p\newline
&=(1+1)^p\newline
&=1+\dbinom{p}{1}+\dbinom{p}{2}+\dots+\dbinom{p}{p-1}+1\newline
\end{aligned}
$$

$$
\therefore 2^p\equiv 2 \pmod p
$$

假设 $a=k$ 时成立。

当 $a=k+1$ 时

$$
\begin{aligned}
a^p
&=(k+1)^p\newline
&=k^p+\dbinom{p}{1}k^{p-1}+\dbinom{p}{2}k^{p-2}+\dots+\dbinom{p}{p-1}k+1\newline
\end{aligned}
$$

$$
\therefore a^p\equiv k^p+1 \pmod p\newline
又\because k^p\equiv k\pmod p\newline
\therefore a^p\equiv k+1\pmod p\newline
\therefore a^p\equiv a\pmod p
$$

由此可得在正整数域中命题成立。

证毕。

上面这个东西就是费马小定理及其在组合意义下使用数学归纳法的证明。

教练布置的作业。

然后费马小定理在 OI 中的常见运用是，$a^{p-2}\equiv a\pmod p\to a^{p-1}\equiv 1\pmod p\to a\times a^{p-2}\equiv 1\pmod p$。

也就是说对于质数 $p$，只要满足 $\gcd(a,p)=1$ 那么 $a^{p-2}$ 即为 $a$ 在模 $p$ 意义下的乘法逆元。这样我们就可以单次 $\log$ 使用快速幂计算逆元。

在欧拉定理中有 $a^{\varphi(n)}\equiv 1\pmod n$。

其中 $\varphi(n)$ 是 $\sum\limits_{i=1}^{i<n}[\gcd(n,i)=1]$，即 $[1,n-1]$ 中与 $n$ 互质的数的个数。具体定义是 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},\varphi(n)=p_1^{a_1-1}p_2^{a_2-1}\cdots p_k^{a_k-1}(p_1-1)(p_2-1)\cdots(p_k-1)$。

费马小定理就是欧拉定理中一个特殊的例子，当 $p$ 为质数时 $\varphi(p)=p-1$。