大家好,欢迎来到IT知识分享网。
历史沿革
该定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的,尽管这对师生都未能给出证明。华林于1770年提出该定理,1773年由拉格朗日首次证明。
定理内容
当且仅当p为素数时:
或者用其它的表述方法:
- 当p为素数时,\((p-1)!+1\)可以被p整除
- 逆定理:若\((p-1)!+1\)可以被p整除,那么p为素数
背景知识
剩余类与剩余系
- 剩余类
定义:一个整数被正整数n除后,余数有n种情形:0,1,2,3,…,n-1,它们彼此对模n不同余。这表明,每个整数恰与这n个整数中某一个对模n同余。这样一来,按模n是否同余对整数集进行分类,可以将整数集分成n个两两不相交的子集。我们把(所有)对模n同余的整数构成的一个集合叫做模n的一个剩余类。
理解:在模n的情况下,余数会有n种情况,那么对于所有的整数来说,就可以根据模n余数划分出n类,每一类中的数模n的余数都相同,而这些类就是一个个的剩余类。
性质:模n的剩余类有n个。 - 剩余系:
定义:指对于某一个特定的正整数n,一个整数集中的数模n所得的余数域。(这里的余数可以不完全/个数小于n) - 完全剩余系:
如果一个剩余系中包含了这个正整数所有可能的余数(一般地,对于任意正整数n,有n个余数:0,1,2,…,n-1),那么就被称为是模n的一个完全剩余系。
只要它们的余数不相同,它们可以不是相邻的数。 - 最小非负剩余系:
如果模n的剩余系为:0、1、2、……、n-1,那么这个剩余系称为最小非负剩余系。 - 最小正剩余系:
将最小非负剩余系中的0换为n,即是最小正剩余系。
缩系(简化剩余系,既约剩余系)
在模n的剩余类中,如果有一个数与n互素,那么该剩余类中的每一个数都与n互素,称该剩余类与n互素。在欧拉定理中([[数论四大定理——欧拉定理]]),欧拉函数\(\varphi (n)\)就等于小于n的正整数中与n互素元素的个数。而这些元素也组成了一个缩系。或者说:在模n的完全剩余系中,有\(\varphi(n)\)个数与n互素,称这\(\varphi(n)\)个数构成了模n的一个缩系。所以欧拉函数也等于一个缩系中元素的个数。
性质:如果元素:
是模n的一个缩系,那么:
也是模n的一个缩系。
证明
必要性
假设p不是素数,设a是p的(素)因子,易知:
(因为(p-1)!包括从1到p-1之间的所有数,而a是p的素因子,a一定小于p,所以在p-1的阶乘中一定有一个a)
则有:\(a\nmid (p-1)!-1\)
而\(p\mid (p-1)!+1\Rightarrow a\mid (p-1)!-1\),前后矛盾
所以p一定是质数。
充分性
思路
证明集合 \(\{2,3,\cdots,p-2\}{2,3,⋯,p−2}\)中存在两两配对的元素a , b ,有\(ab\equiv1(mod\ p)\)。即\((p-2)!\equiv1(mod\ p)\),又\(p-1\equiv-1(mod\ p)\),所以有\((p-1)!\equiv-1(mod\ p)\)
过程
当\(p=2、3\)时,\((p-1)!\equiv -1(mod\ p)\)显然成立(条件中要求了p应为质数/素数,所以跳过4)
当\(p\geq 5\)时,令
\(\forall a\in M\),令:
注意到\(\forall t\in S,p\nmid t\)
\(\therefore \forall t_1,t_2\in S,t_1\lt t_2\Rightarrow t_2-t_1\in S\Rightarrow p\nmid (t_2-t_1)\)
证明S中的元素不同余:
若\(t_1,t_2\)同余,那么有\(t_2-t_1\equiv 0(mod\ p)\Rightarrow t_2-t_1=k*p\),这与前面的结论(\(t_2-t_1\in S\)、\(p\nmid t\))矛盾,所以\(t_1,t_2\)不矛盾。
\(\therefore S\ mod\ p=N\)
也就是\(\forall a\in M,\exists x\in N\),一定有\(ax\equiv 1(mod\ p)\)(注释:因为a可以取到M中的所有元素,而a乘小于p的正整数模p总会出现一个1,所以就可以得知M中所有元素都可以取到逆元)
若\(x=1\),则\(ax\%p=a\%p=a\)
\(\therefore x\ne 1\)
若\(x=p-1\),则\(ax\%p=(ap-a)\%p=[(a-1)p+p-a]\%p=p-a\)
\(\therefore x\ne p-1\)
若\(x=p-1\),则\(a^2\equiv 1(mod\ p)\Rightarrow (a+1)(a-1)\equiv 0(mod\ p)\Rightarrow a=1\)或\(a=p-1\)(\(a=(-1\%p)=p-1\))
\(\therefore x\ne a\)
综上,\(\forall a\in M,\exists x\in M\),且\(a\ne x\),有\(ax\equiv 1(mod\ p)\)
所以\((p-1)!\equiv 1\cdot (p-1)\equiv -1(mod\ p)\)
参考:
- 数论四大定理之威尔逊定理
- 威尔逊定理 数论
- 收集整理威尔逊定理的证明
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30208.html