威尔逊定理

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即：当且仅当p为素数时：

$(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)$

但是由于阶乘是呈爆炸增长的，其结论对于实际操作完全没有益处。

[证明]

取集合 A = {1,2,3,...p-1}; 则A 构成模p乘法的缩系,即任i∈A ,存在j∈A,使得:

$(ij)\ \equiv\ 1\ (\mbox{mod}\ p)$

那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况

$x^2\ \equiv\ 1\ (\mbox{mod}\ p)$ ;

解得:: $x\ \equiv\ 1\ (\mbox{mod}\ p)$ 或

$x\ \equiv\ p-1\ (\mbox{mod}\ p)$

其余两两配对;故而

$(p-1)!\ \equiv\ 1 * (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)$

个人工具