526互联

学习笔记：费马小定理

发布时间 2023-11-01 17:24:46作者: tsqtsqtsq

费马小定理

定义

若 \(p\) 是质数，且 \(\gcd(a, p) = 1\)，则有 \(a^{p - 1} \equiv 1 \pmod{p}\)。

另一个形式：对于任意整数 \(a\)，有 \(a^p \equiv a \pmod{p}\)。

证明

设一个质数为 \(p\)，我们取一个不为 \(p\) 倍数的数 \(a\)。

构造一个序列：\(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 \]

证明：

因为 \((A_i,p)=1,(A_i\times a,p)=1\)

又因为每一个 \(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\)

\[\begin{aligned} a^{p-1}\times f &\equiv f \pmod p \\ a^{p-1} &\equiv 1 \pmod p \end{aligned} \]

证毕。

也可用归纳法证明：

显然 \(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 \]

因为 \(\displaystyle\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!}\) 对于 \(1\leq k\leq p-1\) 成立，在模 \(p\) 意义下 \(\displaystyle\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\) 得证。

证毕。

应用

费马小定理可以用来求逆元。

若 \(p\) 是质数，且 \(\gcd(a,p)=1\)，则有 \(a^{p-1}\equiv1 \pmod p\)。

由乘法逆元定义推导可知 \(a\times\operatorname{inv}(a)\equiv1\equiv a^{p-1} \pmod p\)，于是有：

\[\operatorname{inv}(a)\equiv a^{p-2} \pmod p \\ \]

也就是说，要求 \(a\) 在模 \(p\) 意义下的乘法逆元，只要求 \(a^{p-2}\) 即可。至于乘方的话可以用快速幂浅浅优化一下。

int qpow(int a, int b){
    int res = 1;
    while(b > 0){
        if(b & 1){res *= a;res %= p;}
        a *= a;a %= p;b >>= 1;
    }
    return res;
}
int inv(int n, int p){return qpow(n, p - 2);}