已知n 为一个正整数，且2的n次方减1 是一个质数， 求证n也是质数。

Question

如题所述

Answer 1

用反证法：
假设n不是质数，则n肯定可以分解为两个大于1的数相乘
设n=a×b（a,b都是大于1的正整数）
则2的n次方减1，就是2的ab次方减1
设m=2的a次方，因为a>1,所以m>2
2的n次方减1，可变换为m的b次方减1
当b为奇数时，
m的b次方减1
=(m-1)(m的b-1次方 - m的b-2次方 + m的b-3次方 -……- m + 1）
当b为偶数时，
m的b次方减1
=(m-1)(m的b-1次方 - m的b-2次方 + m的b-3次方 -……+ m - 1）

无论b是奇数或者偶数，m的b次方减1 都能被 m-1 整除
上面提到m>2,所以m-1>1
一个能被大于1的数整除的数，肯定不是质数
即2的n次方减1不是质数
这和题意相矛盾，所以假设不成立，n是质数

Answer 2

2^n-1可写成2进制:11111...1111共n位

用反证法

假设n为合数(n=p*q)

111...111(n位)能整除11..11(P位)

即2^n-1不是质数.

故如2＾n-1是质数，n必为质数

Answer 3

假设 n是合数 n=P*Q则 2^n-1=(2^P)^Q-1=(2^P-1)*(一大堆东西) 因为 P>=2 所以此时它是合数 矛盾 呵呵出来了