一个素数问题

amok

程序设计当中需要证明一个定式 ： 如果 2的p次幂减一为素数，那么p也是素数
怎么证明呢，谢谢高手

twosteps

这个, 这个, 这个不是那么回事吧....
P=11 , 是最小的一个不符合这个定式的PRIM.......

gaga

原帖由 twosteps 于 2005-12-14 13:15 发表
这个, 这个, 这个不是那么回事吧....
P=11 , 是最小的一个不符合这个定式的PRIM.......

2^11 - 1 = 2047 = 89 * 23

btw, 楼主的问题是数学问题不是编程问题吧？

Capfish

楼上两位的反驳有点儿问题吧
楼主的题社是：
2的p次幂减一是素数————>p是素数

楼上两位的例子似乎驳的是
p是素数————>2的p次幂减一是素数

似乎不一样吧，不过没有证明过，不能给出结论，呵呵

twosteps

原帖由 Capfish 于 2006-1-6 00:01 发表
楼上两位的反驳有点儿问题吧
楼主的题社是：
2的p次幂减一是素数————>p是素数

楼上两位的例子似乎驳的是
p是素数————>2的p次幂减一是素数

似乎不一样吧，不过没有证明过，不能给出结论，呵呵

你说的有道理, 我傻了.........$错了$

而且你的思路很正确, 楼住的问题可以证那个AEQUIVALENZ, 就是说, 证:
\not  p是素数————>\not 2的p次幂减一是素数

然后就简单了~~~~

thinkbest

ls, 好像有反例：
p = 4, 2^4 - 1 = 15。

twosteps

原帖由 thinkbest 于 2006-1-6 15:53 发表
ls, 好像有反例：
p = 4, 2^4 - 1 = 15。

这是是反例么? :o

Capfish

嗯，证
not p为素数————> not 2^p-1为素数
1。当p<=1时，显然成立
2。当p>1时
  p＝a×b(a!=1,b!=1)
2^(a*b)-1=(2^a-1)(2^a(b-1)+2^a(b-2)+......+2^a+1)
这个用除法，用2^(a*b)去除以(2^a-1)可以得到
由于a，b都不为0，所以 2^(a*b)-1=m*n，m，n！＝1，不为素数

完毕。。。。
不知道对不对～

twosteps

原帖由 Capfish 于 2006-1-7 06:35 发表
嗯，证
not p为素数————> not 2^p-1为素数
1。当p<=1时，显然成立
2。当p>1时
  p＝a×b(a!=1,b!=1)
2^(a*b)-1=(2^a-1)(2^a(b-1)+2^a(b-2)+......+2^a+1)
这个用除法，用2^(a*b)去除以(2^a-1 ...

就是这个意思~~~~:)

Capfish

嗯，斑竹也不鼓励一下新人么，呵呵