看到老外网站上有个数论的题目，证明一下，练练脑筋。
假设(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),因此上述的数学归纳法证明没有必要了。
本文转自cnn23711151CTO博客，原文链接：http://blog.51cto.com/cnn237111/1197453 ，如需转载请自行联系原作者
