题目

设f(n)=2^n-1,n是正自然数.当n是怎样的自然数时,f(n)是合数?并证明!

提问时间：2020-07-24

答案

当n>3,是偶数或是3的倍数时,f(n)是合数
证明：
(1)
令n=2m,n是偶数
f(n)=2^n-1=2^(2m)-1=(2^m)^2-1=(2^m+1)(2^m-1)
由上可知,只要2^m+1和2^m-1大于1时,f(n)是合数
即当m>=2时,f(n)是合数
即当n是大于3的偶数时,f(n)是合数
(2)
令n=3m,m是自然数
f(n)=2^n-1=2^(3m)-1=(2^m)^3-1=(2^m-1)[2^(2m)+2^m+1]
由上可知,只要(2^m-1)和[2^(2m)+2^m+1]大于1时,f(n)是合数
即当m>=2时,f(n)是合数
即当n大于3,且是3的倍数时,f(n)是合数
----------------------------------------
另外,当n为其它数时,f(n)也有不少是合数,目前还没找到规律,嘿嘿
2^11-1=2047=89*23
2^23-1=8388607=178481*47
2^25-1=33554431=1082401*31
2^29-1=536870911=2304167*233