威尔逊定理

最早由英国的威尔逊爵士提出

一个大于 (1) 的自然数为 (p) ，则它为质数的充要条件为 ((p-1)!equiv -1(mod p))

证明：

充分性我们使用反证法：设 (p) 是合数，则设其最小质因子为 (a)

由于 (a<p) 故 (aleq p-1) 因此 (amid (p-1)!)

所以 (a mid [(p-1)!+1])

又因为 ((p-1)!equiv -1(mod p)) 因此 (pmid [(p-1)!+1])

由 (amid p) 得出 (amid [(p-1)!+1]) 矛盾

因此 (p) 不为合数

故 (p) 为质数

必要性我们这么来考虑：

首先 (2-1equiv -1equiv 1equiv 1!(mod 2))

对于任意质数 (p) 考虑整数 (nin[1,p-1]igcap Z) 令 (ncdot nequiv 1(mod p))

解得 (nequiv pm1(mod p))

所以，对于除了 (1) 与 (p-1) 的所有数，一定存在 (m) 使得 (nmequiv 1(mod p))

而除了 (2) 的所有质数一定为奇数，则剩余的 ((p-3)) 个数一定两两配对，乘积为 (1)

因此 (displaystyle (p-1)!equiv 1cdotprod_{i=2}^{p-2}icdot (p-1)=1cdot 1cdot (-1)equiv -1(mod p))

费马定理

对于整数 (p) ，任意非 (p) 倍数的整数 (a) ，一定有 (a^{p-1}equiv 1(mod p))

考虑到对 (forall n<p,na mid p)

因此 ([a]) 为 (p) 的一个简化剩余类， ([na]) 也为一个简化剩余类

对 (forall n<p,[na]) 互不相同

故 (displaystyle prod_{i=1}^{p-1}(ia)equiv prod_{i=1}^{p-1}i(mod p))

( herefore displaystyle (p-1)!cdot a^{p-1}equiv (p-1)!(mod p))

由威尔逊定理得到 (-1cdot a^{p-1}equiv -1(mod p))

因此得到费马小定理 (a^{p-1}equiv 1(mod p))

当然，费马定理还有其它的形式，例如： (a^pequiv a(mod p))

由 (a^{p-1}equiv 1(mod p)) 得

(a^nequiv (a^{p-1})^{n/(p-1)}cdot a^{nmod (p-1)}equiv 1^{n/(p-1)}cdot a^{nmod (p-1)}=a^{nmod (p-1)}(mod p))

因此，对于求与模数互质整数很大的次方，可以用该方法优化