数论四大定理——威尔逊定理

数论四大定理——威尔逊定理历史沿革该定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的,尽管这对师生都未能给出证明。华林于1770年提出该定理,1773年由拉格朗日首次证明。定理内容当且仅当p为素数时:\[(p-1)!\equiv-1(mod\p)\]或者用其它的表述方法:当p为

大家好,欢迎来到IT知识分享网。

历史沿革

该定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的,尽管这对师生都未能给出证明。华林于1770年提出该定理,1773年由拉格朗日首次证明。

定理内容

当且仅当p为素数时:

\[(p-1)!\equiv -1(mod\ p) \]

或者用其它的表述方法:

  1. 当p为素数时,\((p-1)!+1\)可以被p整除
  2. 逆定理:若\((p-1)!+1\)可以被p整除,那么p为素数

背景知识

剩余类与剩余系

  1. 剩余类
    定义:一个整数被正整数n除后,余数有n种情形:0,1,2,3,…,n-1,它们彼此对模n不同余。这表明,每个整数恰与这n个整数中某一个对模n同余。这样一来,按模n是否同余对整数集进行分类,可以将整数集分成n个两两不相交的子集。我们把(所有)对模n同余的整数构成的一个集合叫做模n的一个剩余类。
    理解:在模n的情况下,余数会有n种情况,那么对于所有的整数来说,就可以根据模n余数划分出n类,每一类中的数模n的余数都相同,而这些类就是一个个的剩余类。
    性质:模n的剩余类有n个。
  2. 剩余系:
    定义:指对于某一个特定的正整数n,一个整数集中的数模n所得的余数域。(这里的余数可以不完全/个数小于n)
  3. 完全剩余系:
    如果一个剩余系中包含了这个正整数所有可能的余数(一般地,对于任意正整数n,有n个余数:0,1,2,…,n-1),那么就被称为是模n的一个完全剩余系。
    只要它们的余数不相同,它们可以不是相邻的数。
  4. 最小非负剩余系:
    如果模n的剩余系为:0、1、2、……、n-1,那么这个剩余系称为最小非负剩余系。
  5. 最小正剩余系:
    将最小非负剩余系中的0换为n,即是最小正剩余系。

缩系(简化剩余系,既约剩余系)

在模n的剩余类中,如果有一个数与n互素,那么该剩余类中的每一个数都与n互素,称该剩余类与n互素。在欧拉定理中([[数论四大定理——欧拉定理]]),欧拉函数\(\varphi (n)\)就等于小于n的正整数中与n互素元素的个数。而这些元素也组成了一个缩系。或者说:在模n的完全剩余系中,有\(\varphi(n)\)个数与n互素,称这\(\varphi(n)\)个数构成了模n的一个缩系。所以欧拉函数也等于一个缩系中元素的个数。
性质:如果元素:

\[r_1,r_2,r_3,…,r_n \]

是模n的一个缩系,那么:

\[ar_1,ar_2,ar_3,…ar_n\ \ \ \ \ \ \ (gcd(a,n)=1) \]

也是模n的一个缩系。

证明

必要性

\[(p-1)!\equiv -1(mod\ p) \Leftrightarrow p|(p-1)!+1 \]

假设p不是素数,设a是p的(素)因子,易知:

\[a\mid(p-1)! \]

(因为(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\)时,令

\[M=\{2,3,4,…,p-2\},N=\{1,2,3,…,p-1\} \]

\(\forall a\in M\),令:

\[S=a\cdot N=\{a,2a,…,(p-1)a\} \]

注意到\(\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)\)

参考:

  1. 数论四大定理之威尔逊定理
  2. 威尔逊定理 数论
  3. 收集整理威尔逊定理的证明

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30208.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信