看到老外网站上有个数论的题目，证明一下，练练脑筋。 假设(2^n)-1是质数，则求证n肯定是质数。 证明如下：反证法 假设(2^n)-1是质数，但n是合数，n=a*b.(a>1,b>1,a,b都是整数) 即2^ab-1为质数。 接下来证明(2^ab)-1必定为合数. 先证明：对于任意x^n-1 （x>2，n>2）,都能因式分解为(x-1)M的一个多项式，其中M为一个多项式。 数学归纳法证明 对于n=2的时候 x^2-1=(x-1)(x+1) 假设对于n=k的时候 x^k-1=(x-1)M,M为一个多项式 则当n=k+1时候 x^(k+1)-1=x*x^k-1=x(x^k-1)+x-1=x(x-1)M+x-1=(x-1)(xM+1) 因此也能分解为含有x-1的多项式。 根据上述证明，(2^ab)-1=((2^a)^b)-1必定能分解成((2^a)-1)M，其中M为一个多项式。由于a>1,必定(2^a)-1>1 因此(2^ab)-1必定为一个合数。 即与2^n-1为质数矛盾，因此n不可能为合数。 ------------------------------------------------------- 刚发现 a^n-1=(a-1)(a^(n-1)+a^(n-2)+....a+1),因此上述的数学归纳法证明没有必要了。