作业帮设M=2^p-1,p为质数,证明,M 的质因数均大于p
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/08 23:47:49
设M=2^p-1,p为质数,证明,M 的质因数均大于p
设M=2^p-1,p为质数,证明,M 的质因数均大于p
设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.
个人对离散数学的范围不太清楚,