设M=2^p-1,p为质数,证明,M 的质因数均大于p
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/29 11:50:41
设M=2^p-1,p为质数,证明,M 的质因数均大于p
这基本上是一个数论题目,不知你对同余,Fermat小定理是否熟悉?
在数论中可用以下两个结论证明 (这两个结论我就不证了):
① 若正整数a,m,n,k满足a^m ≡ a^n ≡ 1 (mod k),则对m,n的最大公约数d,有a^d ≡ 1 (mod k).
② (Fermat小定理)若q为质数,a不是q的倍数,则a^(q-1) ≡ 1 (mod q).
原题证明:设q是M = 2^p-1的一个质因数,即有2^p ≡ 1 (mod q).
由②,有2^(q-1) ≡ 1 (mod q) (易见2不是q的倍数).
考虑p和q-1的最大公约数d,由p是质数,有d = 1或p.
而由①,2^d ≡ 1 (mod q),可知d ≠ 1,即d = p.
于是q-1 > 0作为d = p的倍数,有q-1 ≥ p,即q > p.
在抽象代数中可以用群论的知识来证明:
设q是M = 2^p-1的一个质因数,考虑mod q的剩余类环Z/qZ = {0,1,...,q-1}.
由q是质数,其中的非零元都是(乘法)可逆元.
全体可逆元构成的乘法群(Z/qZ)*是q-1阶群,以1为单位元.
考虑2在(Z/qZ)*中生成的子群 = {1,2,2²,2³,...},设其阶数为r,则是一个r阶循环群.
由q | 2^p-1,可知在mod q意义下2^p = 1,于是可得r | p.
由p是质数,有r = 1或p,但显然r ≠ 1,即有r = p.
而作为(Z/qZ)*的子群,由Lagrange定理,其阶数r = p整除(Z/qZ)*的阶数 = q-1.
于是q-1 ≥ p,即q > p.
个人对离散数学的范围不太清楚,
在数论中可用以下两个结论证明 (这两个结论我就不证了):
① 若正整数a,m,n,k满足a^m ≡ a^n ≡ 1 (mod k),则对m,n的最大公约数d,有a^d ≡ 1 (mod k).
② (Fermat小定理)若q为质数,a不是q的倍数,则a^(q-1) ≡ 1 (mod q).
原题证明:设q是M = 2^p-1的一个质因数,即有2^p ≡ 1 (mod q).
由②,有2^(q-1) ≡ 1 (mod q) (易见2不是q的倍数).
考虑p和q-1的最大公约数d,由p是质数,有d = 1或p.
而由①,2^d ≡ 1 (mod q),可知d ≠ 1,即d = p.
于是q-1 > 0作为d = p的倍数,有q-1 ≥ p,即q > p.
在抽象代数中可以用群论的知识来证明:
设q是M = 2^p-1的一个质因数,考虑mod q的剩余类环Z/qZ = {0,1,...,q-1}.
由q是质数,其中的非零元都是(乘法)可逆元.
全体可逆元构成的乘法群(Z/qZ)*是q-1阶群,以1为单位元.
考虑2在(Z/qZ)*中生成的子群 = {1,2,2²,2³,...},设其阶数为r,则是一个r阶循环群.
由q | 2^p-1,可知在mod q意义下2^p = 1,于是可得r | p.
由p是质数,有r = 1或p,但显然r ≠ 1,即有r = p.
而作为(Z/qZ)*的子群,由Lagrange定理,其阶数r = p整除(Z/qZ)*的阶数 = q-1.
于是q-1 ≥ p,即q > p.
个人对离散数学的范围不太清楚,
设n为大于2的正整数,证明:存在一个质数p,满足n
设P是大于3的质数,证明P²-1能被24整除.
P的平方+M的平方=N的平方,其中P味质数,M,N为自然数.求证:2(P+M+1)是完全平方数
5(m+n+p)=mnp m,n,p为质数,求n,m,p的值
设p是大于3的质数,求证:11p^2+1是12的倍数
p是一个大于3的质数,证明p^2-1可以被24整除
如果P与P+2都是大于3的质数,那么请证明6是P+1的约数
2小于m小于p,m、p为整数,m不为p的因子.当m、p的最大公约数是2时,能否推出p除以m的余数大于1或等于1.
若P为大于5的质数,P*2-1是24的倍数
设M,P是两个非空集合,定义M与P的差集为M-P={x|x∈M且x∉P},求证M-(M-P)=M∩P
设P,M为两个非空数集,定义P*M={ (X,Y)|X∈P,Y∈M},若P={ 1,2},M={1,2,3},求(P*M
设p大于3,为质数,求证3能整除p的平方减1的差