威尔逊定理

跳转到：导航, 搜索

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

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

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

[编辑] 证明

若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)$

若p不是素数则易知有d=gcd(p,(p-1)!)=p

故而

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