威尔逊定理
威尔逊定理：当 ( p − 1 ) ! ≡ − 1 ( m o d p ) ( p -1 )! ≡ -1 ( mod p ) (p−1)!≡−1(modp) 时， p p p为素数。
p ∣ ( p − 1 ) ! + 1 p|(p-1)!+1 p∣(p−1)!+1
即
( p − 1 ) ! ≡ ( p − 1 ) ≡ − 1 ( m o d p ) (p – 1)! \equiv (p -1) \equiv-1(mod \ p) (p−1)!≡(p−1)≡−1(mod p)
证明（静下心看）：
先假设集合 M = { 2 , 3 , 4 , ⋯ , p − 2 } M=\{ 2,3,4,\cdots,p – 2\} M={
2,3,4,⋯,p−2} ，集合 N = { 1 , 2 , 3 , ⋯ , p − 1 } N = \{ 1,2,3,\cdots,p-1\} N={
1,2,3,⋯,p−1}
任取一个 a ∈ M a\in M a∈M ， a a a 一定与 p p p 互质。
再假设一个集合 S = a ⋅ N = { a , 2 a , ⋯ , a ( p − 1 ) } S=a\cdot N=\{a,2a,\cdots, a(p-1)\} S=a⋅N={
a,2a,⋯,a(p−1)} ，对于 ∀ x ∈ N \forall x\in N ∀x∈N ， x x x 一定与 p p p 互质。
则 S ≡ N ( m o d p ) S\equiv N (mod \quad p) S≡N(modp) （任何数 m o d p mod \quad p modp 一定属于 { 1 , 2 , ⋯ , p − 1 } \{1,2,\cdots ,p-1\} {
1,2,⋯,p−1} 即 N N N）。
即 ∀ a ∈ M \forall a\in M ∀a∈M ， ∃ x ∈ N \exist x \in N ∃x∈N ， a x ≡ 1 ax \equiv 1 ax≡1（因为 a x ∈ S ax \in S ax∈S ，在 m o d p mod \ \ p mod p 的条件下 S = N S=N S=N ，且存在 1 ∈ N 1\in N 1∈N）
我们可以证明，当 x = 1 x=1 x=1 或 x = p − 1 x=p-1 x=p−1 或 x = a x=a x=a 时，与已知矛盾。
对于 ( p − 1 ) ! (p-1)! (p−1)! ，有
2 × ( p − 1 ) ! = 1 × 2 × 3 × ⋯ × ( p − 1 ) × ( p − 1 ) × ( p − 2 ) × ( p − 3 ) × ⋯ × 1 ( m o d p ) 2\times(p-1)!=1 \times 2 \times 3 \times \cdots \times (p-1) \\ \times(p-1)\times(p-2)\times(p-3) \times\cdots \times1 (mod \ \ p) 2×(p−1)!=1×2×3×⋯×(p−1)×(p−1)×(p−2)×(p−3)×⋯×1(mod p)
2 × ( p − 1 ) ! = 2 × ( p − 1 ) ( m o d p ) 2\times(p-1)!=2\times(p-1) (mod \ \ p) 2×(p−1)!=2×(p−1)(mod p)
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/207614.html原文链接：https://javaforall.net
