Prove if prime can be written as $2^n+1$, $n = 2^k$ Prove that if prime can be written as $\ 2^n + 1$ then $n = 2^k$, $\;\;n, k \in \mathbb N$.
I am pretty new in this part of math.
 A: If n is odd, then $2^n+1 = (2+1)\cdot {2^n+1 \over 2+1}  $ where the fraction evaluates to an integer, because this is true even for general bases $b$ : we'll have $b^n+1 = (b+1)\cdot {b^n+1 \over b+1}  $.      
So for odd $n$, except trivially $n=1$, the expression cannot be prime.
Thus $n$ must be even, say $n=2m$ , assume with an odd $m$. Then our initial expression changes to $4^m+1 = (4+1)\cdot {4^m+1 \over 4+1}  $.
We see, that we have the same problem as before: only if $m=1$ an odd $m$ allows the expression to be prime, so also $m$ must be even, say $m=2l$.
Repeat this to see that only numbers $n=2^k$ allow a prime solution of your exponential expression.
A: Expand the following:
$2^{3m}+1=(2^m+1)(2^{2m}-2^m+1)\\
2^{5m}+1=(2^m+1)(2^{4m}-2^{3m}+2^{2m}-2^m+1)$
A: I think the easier way is proving that if $n\ne 2^k$ then $2^n+1$ is not prime.
To do this just take modulus $3$:
$2 = 2\; (\operatorname{mod}\; 3)$
$2\cdot2 = 1\; (\operatorname{mod}\; 3)$
So $2^(2^k)$ is congruent to $1$ mod $3$ as $(2^2)^k = 1^k = 1$ mod $3$.
But if $n \ne 2^k$, then $n$ will have an odd factor or $n$ will be odd itself, and we will have a $2$ 'unpaired', so we would have 
$2^n = 1\cdot 2 = 2$ mod $3$
and hence, if $n$ is not a power of two:
$2^n + 1 = 2 +1 = 0$ mod $3$, 
so $p$ can't be prime
but if $n$ is a power of $2$ then
$2^n +1 = 1 + 1 = 2$ mod $3$, so this doesn't guarantee us that $p$ MUST be prime, but this shows that $p$ CAN be prime.
