费马小定理（Fermat's little theorem）

如果 \(p\) 是一个质数，而整数 \(a\) 不是 \(p\) 的倍数，则有 \(a^{(p-1)} \equiv 1 \pmod p\)。

换句话说，对于任意整数 \(a\)，有 \(a^p \equiv a \pmod{p}\)。

证明

设一个质数 \(p\) 、一个整数 \(a\) 满足 \(a \bmod p \neq 0\)，

构造一个序列：\(A=\{1,2,3\dots,p-1\}\)，该序列满足以下性质：

\[\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p \]

证明 1：

因为

\[(A_i,p)=1,(A_i\times a,p)=1 \]

又因为

有且只有一个 \(i\) 满足 \(A_i\times a \pmod p\) ，且 \(A_i\times a \pmod p < p\)

即每一个 \(A_i\times a\) 都对应了一个 \(A_i\)，

得证。

设 \(f=(p-1)!\) ，则有

\[f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p \]

又有

\[a^{p-1}\times f \equiv f \pmod p \\ a^{p-1} \equiv 1 \pmod p \]

证毕。

证明 2：

归纳法。

显然有 \(1^p\equiv 1\pmod p\)，假设 \(a^p\equiv a\pmod p\) 成立，那么通过二项式定理有

\[(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1 \]

因为

\[\binom{p}{k}=\cfrac{p(p-1)\cdots (p-k+1)}{k!} \]

对于 \(1\leq k\leq p-1\) 成立，在模 \(p\) 意义下有

\[\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p \]

那么

\[(a+1)^p \equiv a^p +1\pmod p \]

将 \(a^p\equiv a\pmod p\) 带入得

\[(a+1)^p\equiv a+1\pmod p \]

证毕。

应用

求 \(a\) 的 \(b\) 次方对 \(n\) 取模。

代码：

int Fmt(int a, int b, int m) //废妈小定理
{
	int t = 1;
	int y = a;

	while (!b)
	{
		if (b & 1 == 1)
			t = t * y % m;
		y = y * y % m;
		b >>= b;
	}
	return t;
}