费马小定理

定义

(a^{p - 1} equiv 1 pmod p)
变式: $a^{p - 2} equiv dfrac{1}{a} pmod p Leftrightarrow a imes a^{p - 2} equiv 1 pmod p $

前提

(p) 是质数, 且 (a) 不是 (p)的质数

方法

直接快速幂取模就行

code

inline ll q_pow(ll x, ll y, int mod) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = (ans * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return ans;
}
inline int fermat(int a, int mod) {
	return f_pow(a, mod - 2);
}

引理1

若 (a,b,c) 为 (3) 个整数, (m) 为正整数, 且 ((m,c) = 1), 则当 (ac equiv bc pmod m) 时,有 (a equiv b pmod m)

引理2

设 (m) 是一个整数且 (m > 1), (b) 是一个整数且 ((m,b) = 1). 如果 (a_1, a_2, a_3...a_m) 是模 (m) 的一个完全剩余系, 则 (ba_1, ba_2, b_a3...ba_m) 也构成模 (m) 的一个完全剩余系
完全剩余系请读者自己上维基百科

引理1证明

(ac equiv bc pmod m)
可得 (ac-bc equiv 0 pmod m)
可得 ((a-b)c equiv 0 pmod m)
因为 ((m,c) = 1)
即 (m,c) 互质
(c) 可以约去
(a-b equiv 0 pmod m)
可得 (a equiv b pmod m)

引理2证明

反证法:
若将 (2) 个整数 (ba_i) 和 (ba_j) 同余
即 (ba_i equiv ba_j pmod m (i geqslant 1 且 j geqslant 1))
根据引理1
则 (a_i equiv a_j pmod m)
由完全剩余系的定义知这是不可能的
因此不存在 (2) 个整数 (ba_i) 和 (ba_j) 同余
所以 (ba_1, ba_2, b_a3...ba_m) 构成模 (m) 的一个完全剩余系

费马语言证明

构造素数 (p) 的完全剩余系
(P = {1, 2, 3, p - 1})
因为 ((a, p) = 1), 由引理2可得
(A = {a, 2a, 3a, (p - 1)a})
也是 (p) 的一个完全剩余系, 由完全剩余系的性质得
(1 imes 2 imes 3 imes ... imes (p - 1) equiv a imes 2a imes 3a imes ... imes (p - 1)a pmod p)
即 ((p - 1)! equiv (p - 1)! imes a{p-1} pmod p)
又因为 (((p - 1)!, p) = 1) 同余两边可约去 ((p - 1)!), 得
(a^{p - 1} equiv 1 pmod p)

费马图形证明

请参考图形证明