费马小定理

(Updated: )
算法 › 费马小定理

威尔逊定理

若$p$是素数, 则$(p-1)! = -1 (mod p)$
逆定理也成立, 可以用来判断素数

费马小定理

若$p$是素数, $a$是一个正整数, 且$p !| a$, 则$a^{p-1} \equiv 1 (mo d p)$

证明

对于$a, 2a, 3a, \dots ,(p-1)a$是模$p$的最小正剩余类, 那么
$$a \cdot 2a \cdot \dots (p-1)a \equiv 1 \cdot 2 \dots \cdot (p-1) (mo dp)$$
即
$$a^{p-1}(p-1)! \equiv (p-1)! (mo dp)$$
消去$(p-1)!$得到:
$$
a^{p-1} \equiv 1 (mo dp)
$$

应用

计算逆元

当模的$p$是素数时,
显然$a \cdot a^{p-2} \equiv 1(mo dp)$, 即$a$的逆元为$a^{p-2}$, 可以通过快速幂计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int M = 1e9 + 7;
int qpow(int base, int pow) {
	int ans = 1;
	while(pow) {
		if(pow&1) ans = ans * base % M;
		base = base * base % M;
		pow >>= 1; 
	}
	return ans;
}

int rev(int a, int p) {
	return qpow(a, p-2);
}

计算$a^{b^c}$

由于$a^{p-1}\equiv 1(mo dp)$, 那么可以考虑$b^c\equiv m(mo d(p-1))$, 这样最终得到$a^{b^c}\equiv a^{b^c(mo d(p-1))} (mo dp)$

1
2
3
4
5
6
7
8
9
10
11
int qpow(int base, int base, int p) {
	int ans = 1;
	while(pow) {
		if(pow&1) ans = ans * base % p;
		base = base * base % p;
		pow >>= 1;
	}
	return ans;
}

ans = qpow(a,qpow(b,c,p-1),p);