wilson定理

wilson定理

正整数n > 1， 则n是一个素数当且仅当$(n - 1)! \equiv -1 (mod\ n)$

如果n为非质数，假设集合A为${1, x_1, x_2,\cdots x_{m - 1}, n - 1}$与n互质。

对于任意$x_i$，则$x_i \cdot A$集合为${x_i,\ x_i\cdot x_1,\ x_i \cdot x_2,\ \cdots,\ x_i \cdot x_{m - 1},\ x_i \cdot (n - 1)}$, 对于其中$x_i\cdot A$中任意一个元素其膜n的值互不相同，且为集合A中的元素，因此存在$x_i * x_j \equiv 1 (mod\ n)$，因为1和n - 1模n逆元为其本身，$x_i$的逆元为$x_j$
$$
(1\times x_1 \times x_2 \times \cdots x_m \times n - 1) \cdot (1\times x_1 \times x_2 \times \cdots x_m \times n - 1) \equiv (1 * 1) \times (x_i * x_j) \cdots \times ((n - 1) * (n - 1)) \equiv 1 (mod \ n) \\
令(1\times x_1 \times x_2 \times \cdots x_m \times n - 1) = y \\
y^2\equiv 1 (mod\ n)\\
y \equiv 1 (mod\ n)\ 或\ y \equiv n - 1 (mod\ n)
$$

$$
x_i*x_j \equiv x_i * x_k (mod\ n) \\
x_i * (x_j - x_k) \equiv 0 (mod\ n) \\
(x_j - x_k) \equiv 0 (mod\ n) \\
x_j = x_k
$$