为什么说2^n-1是质数,n也是质数?如果说2^n-1是质数,那么n也是质数吗?

Question

为什么说2^n-1是质数,n也是质数?
如果说2^n-1是质数,那么n也是质数吗?

Answer 1

若2^n-1是质数,则n也是质数.这个可以用反证法证明：
若n不是质数,则存在大于1,小于n的两个正整数a,b满足 n=ab.
于是
2^n-1
=2^(ab)-1
=(2^a)^b-1 (令y=2^a)
=y^b-1
=(y-1)(y^(b-1)+y^(b-2)+...+y+1)
容易看出上式中 y-1 与 y^(b-1)+...+1 都不等于1 (否则如果 y-1=1,y=2,即2^a=2,则必有a=1,与a>1 矛盾；如果y^(b-1)+...+y+1=1,则必有 b-1=0,b=1,这与 b>1 矛盾).
因此 y-1 与 y^(b-1)+...+1 都是大于1的正整数,也就是2^n-1的两个大于1的因子,这与 2^n-1 是质数矛盾.
所以若2^n-1是质数,则n也是质数.