# Explaining how $n = 2^r$ for $n$ prime

I found this claim in my textbook while reading the section on prime numbers today:

"If $n$ is a positive integer such that $2^n + 1$ is prime, then $n = 2^r$ for some integer $r \ge 0$."

Where did this result come from? (that is, is there a proof? I cannot find one in my textbook and Google did not help either.)

-
$x^t+1$ can be factored if $t$ is odd. This applies to $2^n+1$ if $n$ has an odd factor. Now check that neither of the two factors is 1. –  Andrés Caicedo Jan 30 '13 at 2:57

## 2 Answers

It comes from

$$x^{2m+1}+y^{2m+1}=(x+y)(x^{2m}-x^{2m-1}y+x^{2m-2}y^2-...+x^{2}y^{2m-2}-xy^{2m-1}+y^{2m})$$

Can you see why this implies that $n$ cannot have any odd divisor? And which numbers have no odd divisors?

-

Hint $\$ If $\rm\:n\:$ had an odd divisor $\rm\,k,\,$ say $\rm\:n = jk\:$ then $\rm\:2^j\!+\!1\:|\:2^n\!+1\:$ since

$\rm\qquad\quad mod\ 2^j\!+1\!:\ \color{#0A0}{2^j}\equiv \color{#C00}{-1}\:\Rightarrow\: n \equiv (\color{#0A0}{2^j})^k\!+1\equiv (\color{#C00}{-1})^k+1\equiv -1+1\equiv 0$

which is $\rm\ \ \ x\!+\!1\:|\:x^k+1\:$ for odd $\rm\,k\$ (for $\rm\ x = 2^j).$

Generally $\rm\:x\!-\!c\:|\:f(x) \iff f(c) = 0\ \$ (Factor Theorem)  Above is case $\rm\:c = -1.$

-