6.特殊的同余式

本章讨论三个理论和应用中很重要的同余式：

1. 威尔逊定理：若 p 是素数，则 p 除 \((p-1)!\) 的余数是 \(-1\)
2. 费马小定理：给出了 \(a^p\) 模 p 的同余式；特别地，若 p 是素数，a 是整数，那么 \(a^p\) 和 a 被 p 除有相同的余数
3. 欧拉定理：将费马小定理推广到模不是素数的情形

应用：

1. 素性检验，因子分解
2. 伪素数；证明素数

1. 威尔逊定理

若 p 是素数，则 \((p-1)!\equiv-1\pmod p\)

证明：

若 \(p=2\)，那么 \((p-1)!+1=(2-1)!+1=0\)，于是 \((p-1)!+1\equiv0\pmod p\)

根据[定理4.10]，对于所有 \(a=1..p-1\)，a 都有最小正整数逆 \(\bar a=1..p-1\)，且 \(a\bar a\equiv 1\pmod p\)

可证：\(\forall i=2..\frac{p-1}2\)，\(i(i+\frac{p-3}2)\equiv1\pmod p\)（提示：根据[定理4.11]，小于 p 的正整数中只有 1 和 \(p-1\) 等于它们自身模 p 的逆）

于是 \(\prod\limits_{i=2}^{p-2}i\equiv1\pmod p\)，蕴涵 \((p-1)!\equiv p-1\pmod p\)

\(\blacksquare\)

假设 n 是正整数，且 \(n\ge2\)

若 \((n-1)!\equiv-1\pmod n\)，那么 n 是素数

证明：\(\neg q\to p\) 不成立

(1)

假设 n 是合数，存在 \(1<a,b<n\) 使得 \(n=ab\)，蕴涵 \(a|(n-1)!,b|(n-1)!\)

若 \(a\ne b\)，那么 \(ab|(n-1)!\)，即 \(n|(n-1)!\)，即 \((n-1)!\equiv 0\pmod n\)

(2)

因为 \((n-1)!\equiv-1\pmod n\)，即 \(n|((n-1)!+1)\)，根据[定理1.8]，\(a|((n-1)!+1)\)

根据[定理1.9] 和 \(a|(n-1)!\) 且 \(a|((n-1)!+1)\)，有 \(a|[((n-1)!+1)-(n-1)!]\)，即 \(a|1\)，即 \(a=1\) 或 \(a=-1\)，这与 \(a\ge2\) 矛盾

\(\blacksquare\)

威尔逊定理及其逆命题给出了一种素性检验方法，但是复杂度不够优秀

而费马小定理用于素性检验的复杂度更加优秀，并且该定理的名字主要用于区别费马大定理

设 p 是素数，a 是正整数，且 \(p\nmid a\)，则 \(a^{p-1}\equiv 1\pmod p\)