求证:如果p是奇素数,那么任何能整除2^p-1的素数q都一定+/-1(mod 8)同余
来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/10/06 04:05:39
求证:如果p是奇素数,那么任何能整除2^p-1的素数q都一定+/-1(mod 8)同余
p是奇素数这个条件有点多余,其实对奇数都成立.
证明用到平方剩余的一个结果:
引理:对奇素数q,若2是mod q的平方剩余 (即存在整数a使a² = 2(mod q)),则q = ±1(mod 8).
由条件2^p = 1(mod q),即有2^(p+1) = 2(mod q).
而p是奇数,可取a = 2^((p+1)/2),则a² = 2(mod q),2是mod q的平方剩余.
于是q = ±1(mod 8).
如果需要补充引理的证明,
再问: 为什么由2是mod q的平方剩余就可以推出q=+/-(mod 8)?
再答: 若a² = 2 (mod q), 由Fermat小定理有2^((q-1)/2) = a^(q-1) = 1 (mod q). q是奇素数, 若q ≠ ±1(mod 8), 则q = ±3(mod 8). 只要证明对奇素数q = ±3(mod 8), 有2^((q-1)/2) = -1 (mod q), 即得矛盾. 对q = 8k+3, 在mod q意义下, 有如下2k+1个等式: 1·(8k+1) = -(8k+2)(8k+1) 3·(8k-1) = -(8k)(8k-1) ... (4k-1)(4k+3) = -(4k+4)(4k+3) 4k+1 = -(4k+2) 相乘得1·3·...·(8k+1) = -(4k+2)(4k+3)...(8k+2) (mod q). 而2·4·...·(8k+2) = 2^(4k+1)·1·2·...·(4k+1) (mod q). 于是(8k+2)! = -2^(4k+1)(8k+2)! (mod q). 由q是素数, (8k+2)! = (q-1)!与q互素, 两边消去得1 = -2^(4k+1) (mod q). 即2^((q-1)/2) = -1 (mod q). 对q = 8k+5, 在mod q意义下, 有如下2k+1个等式: 1·(8k+3) = -(8k+4)(8k+3) 3·(8k+1) = -(8k+2)(8k+1) ... (4k+1)(4k+3) = -(4k+4)(4k+3) 相乘得1·3·...·(8k+3) = -(4k+3)(4k+4)...(8k+4) (mod q). 而2·4·...·(8k+4) = 2^(4k+2)·1·2·...·(4k+2) (mod q). 于是(8k+4)! = -2^(4k+2)(8k+4)! (mod q). 由q是素数, (8k+4)! = (q-1)!与q互素, 两边消去得1 = -2^(4k+2) (mod q). 也即2^((q-1)/2) = -1 (mod q).
证明用到平方剩余的一个结果:
引理:对奇素数q,若2是mod q的平方剩余 (即存在整数a使a² = 2(mod q)),则q = ±1(mod 8).
由条件2^p = 1(mod q),即有2^(p+1) = 2(mod q).
而p是奇数,可取a = 2^((p+1)/2),则a² = 2(mod q),2是mod q的平方剩余.
于是q = ±1(mod 8).
如果需要补充引理的证明,
再问: 为什么由2是mod q的平方剩余就可以推出q=+/-(mod 8)?
再答: 若a² = 2 (mod q), 由Fermat小定理有2^((q-1)/2) = a^(q-1) = 1 (mod q). q是奇素数, 若q ≠ ±1(mod 8), 则q = ±3(mod 8). 只要证明对奇素数q = ±3(mod 8), 有2^((q-1)/2) = -1 (mod q), 即得矛盾. 对q = 8k+3, 在mod q意义下, 有如下2k+1个等式: 1·(8k+1) = -(8k+2)(8k+1) 3·(8k-1) = -(8k)(8k-1) ... (4k-1)(4k+3) = -(4k+4)(4k+3) 4k+1 = -(4k+2) 相乘得1·3·...·(8k+1) = -(4k+2)(4k+3)...(8k+2) (mod q). 而2·4·...·(8k+2) = 2^(4k+1)·1·2·...·(4k+1) (mod q). 于是(8k+2)! = -2^(4k+1)(8k+2)! (mod q). 由q是素数, (8k+2)! = (q-1)!与q互素, 两边消去得1 = -2^(4k+1) (mod q). 即2^((q-1)/2) = -1 (mod q). 对q = 8k+5, 在mod q意义下, 有如下2k+1个等式: 1·(8k+3) = -(8k+4)(8k+3) 3·(8k+1) = -(8k+2)(8k+1) ... (4k+1)(4k+3) = -(4k+4)(4k+3) 相乘得1·3·...·(8k+3) = -(4k+3)(4k+4)...(8k+4) (mod q). 而2·4·...·(8k+4) = 2^(4k+2)·1·2·...·(4k+2) (mod q). 于是(8k+4)! = -2^(4k+2)(8k+4)! (mod q). 由q是素数, (8k+4)! = (q-1)!与q互素, 两边消去得1 = -2^(4k+2) (mod q). 也即2^((q-1)/2) = -1 (mod q).
已知p是素数 求证p整除(p-1)!+1
证明对于任何素数p>3,2*(p-3)!≣-1 (mod p)
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
已知p是不小于5的素数,2p+1也是素数,求证4p+1是合数
设p为素数,n为任意自然数.求证:(1+n)^p-n^p-1 能被p整除.
如果p是素数,a是整数,那么p!|(a^p+(p-1)!a)
设p为大于五的素数,求证240整除(p的四次方-1)
有些素数p=2;617满足a是任一小于p的正整数时a^((p-1)/2)-1均被p整除,称类素数.
证明:如果整数p>1且P是(P-1)!+1的因数,则p一定是素数.
数论 证明奇素数p能表示成两个正整数的平方和的充要条件是p=4m+1
关于同余式的证明证明同余式(-4)^((p-1)/4) = 1 (mod p) ,其中p为模4余1的素数
怎么证明:若P是奇素数,则P|(a的p次方+(p-1)!a)?