威尔逊定理(应用于数学、信息学的定理)

威尔逊定理

应用于数学、信息学的定理

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )，但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

证明

充分性

如果“p”不是素数，当，若p不是平方数，则存在两个不等的因数a，b使得;若p是完全平方数即，

必要性

若p是素数，取集合

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

由此可得:

其余两两配对；故而

必要性证明

证明：若p为质数，则p可整除

方法一

，命题显然成立；

假设B中被p除余一的数是γa:

一若

二若

由一二三知

a不同时，γ也相异；若，因，，而B中的元素关于mod p不同余，可见

即A中的每一个a均可找到与其联会的

又，a不同时，γ也相异。

因此，A中的偶数个

∴

从而p可整除

方法二

对于偶质数2，命题显然成立；

对于奇质数，令中不会有对于除数p同余的两个数；事实上则，B中的元素不可能被p除尽。于是B中被p除得的余数形成集合

假设b中被p除余一的数是γa:

一若

二若

三若，故应有此与矛盾，故不成立；

由一二三知

a不同时，γ也相异；若，因，而B中的元素关于mod p不同余，可见

依次取a为

即

从而

又

则

从而p可整除

参考资料

Warning: Invalid argument supplied for foreach() in /www/wwwroot/newbaike1.com/id.php on line 362

条目作者

小编

资深百科编辑

概述

证明

充分性

必要性

必要性证明

方法一

方法二

参考资料