机械荟萃山庄

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 1929|回复: 3

一个数论小问题

[复制链接]
发表于 2019-4-28 10:01:48 | 显示全部楼层 |阅读模式
设p,q为奇素数。
如果p整除2^q-1,那么p>q么?
比如2^11-1=2047=23*89,可知23和89都大于11

回复

使用道具 举报

 楼主| 发表于 昨天 11:21 | 显示全部楼层
好多年前的问题了,今天无意中被我看到了方法,比想象中的简单,还是在这里写一下吧,虽然我知道没几个人感兴趣
首先,答案是肯定的,即如果p整除梅森数2^q-1,那么p>q;
其次,更进一步地,梅森数2^q-1的所有因数都形如2kp+1,其中k是一个正整数。
理由是这样的,根据费马小定理,2^(q-1)≡1(mod q),再根据梅森数的定义,2^p≡1(mod q),所以gcd(q-1,p)>1。而p是一个素数,所以q-1是p的整数倍,又q-1是一个偶数,所以q-1是p的偶数倍,所以q-1=2kp,q=2kp+1,其中k是一个正整数(可以为1)。

可以用前面几个不是素数的梅森数验证一下
2^11-1 = 23*89                                    (23 = 2*11+1, 89=8*11+1);
2^23-1=47*178481                            (47=2*23+1, 178481=7760*23+1);
2^29-1=233*1103*2089                  (233=8*29+1, 1103=38*29+1, 2089=72*29+1);
2^37-1=223*616318177                  (223=6*37+1, 616318177=16657248*37+1);

点评

https://www.rieselprime.de/ziki/GIMPS_factoring_and_sieving 有兴趣的可以看看 因式分解的三个方法,trial factoring , p-1,ECM  发表于 昨天 11:27
回复 支持 反对

使用道具 举报

31

主题

1045

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
11045
发表于 昨天 19:42 来自手机 | 显示全部楼层
数论,在数学领域都是一个难啃的骨头,普通人应该很少对这个领域感兴趣,而且和一般的工程领域没什么关系,工程师很少涉及,而且这个是真的不懂就是不懂。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|手机版|Archiver|机械荟萃山庄 ( 辽ICP备16011317号-1 )

GMT+8, 2024-12-23 21:40 , Processed in 0.104738 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表