Qn about CS1231SHow to prove that if 2^n+1 is a prime, then n is a power of 2?[默儿 (4-22 23:11, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

That statement is falseCounter example:
2^32+1=4294967297=6700417*641[PvsNP (4-23 0:45, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

(引用 PvsNP:That statement is falseCounter example: 2^32+1=4294967297=6700417*641)you are wrongpls look at the question again. saying if 2^p+1 is a prime, then p is the power of 2. You just showed that the reverse statement is wrong. The original statement is correct.[杨明 (4-23 0:49, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

come inif n is not a power of 2, then there exists an odd prime dividing n, say p. then, n=pq.
then,
2^n+1=2^pq+1=(2^q+1)(2^(p-1)q-2^(p-2)q+...+2^2q-2^q+1)
and p is odd, LHS=RHS.
QED.[杨明 (4-23 0:55, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

(引用 杨明:you are wrongpls look at the question again. saying if 2^p+1 is a prime, then p is the power of 2. You just showed that the reve...)you are right : )[PvsNP (4-23 1:06, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

(引用 杨明:come inif n is not a power of 2, then there exists an odd prime dividing n, say p. then, n=pq. then, 2^n+1=2^pq+1=(2^q+1)(2^(p-1...)强！[PvsNP (4-23 1:12, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼