36
$\begingroup$

A little bird told me that if $2^n+1$ is prime, then $n$ is a power of $2$. I tend not to trust talking birds, so I'm trying to verify that statement independently.

Suppose $n$ is not a power of $2$. Then $n = a \cdot 2^m$ for some $a$ not a power of $2$ and some integer $m$. This gives $2^n+1 = 2^{a \cdot 2^m}+1$. Now I suspect there's a way to factor that, but I don't see how. Can someone give me a hint?

$\endgroup$
5
  • 8
    $\begingroup$ A proof of this fact is also given in Wikipedia article on Fermat primes. $\endgroup$
    – Martin Sleziak
    May 4, 2012 at 10:06
  • $\begingroup$ Neat. I didn't know it had a name. $\endgroup$
    – Rob
    May 4, 2012 at 10:10
  • 3
    $\begingroup$ Disproof: $2^0+1=2$ → $n=2^k=0$? $\endgroup$
    – xoxox
    Feb 18, 2016 at 17:47
  • $\begingroup$ Related: math.stackexchange.com/questions/1213800 $\endgroup$
    – Watson
    Nov 26, 2018 at 10:57
  • $\begingroup$ @xoxox: "where n is a nonnegative integer" $\endgroup$
    – smci
    Mar 9, 2019 at 2:05

1 Answer 1

Reset to default
36
$\begingroup$

Hint. For any odd natural number $a$, the polynomial $x+1$ divides $x^a+1$ evenly.

In particular, we have $$ \frac{x^a+1}{x+1}=\frac{(-x)^a-1}{(-x)-1}=1-x+x^2-\cdots+ (-x)^{a-1}$$ by the geometric sum formula. In this case, specialize to $x=2^{2^{\large m}}$ and we have a nontrivial divisor. (Also, $x^a+1\equiv(-1)^a+1\equiv-1+1\equiv0\mod x+1$ inside $\Bbb Z[ x]$ is pretty slick.)

$\endgroup$
3
  • 2
    $\begingroup$ Hi, sorry for a late post, but could you explain your answer a bit more for me. Did you mean to say, set $x = 2^m$ instead of $x = 2^{2^m}$ $\endgroup$
    – Tyler Hilton
    Jan 28, 2013 at 8:01
  • 7
    $\begingroup$ @TylerHilton No, I meant $x=2^{2^m}$ as I wrote. If $n=a2^m$ with $a$ odd, then this shows that $2^{2^m}+1$ divides $2^{a2^m}+1=2^n+1$, and hence $2^n+1$ is composite when $n$ is not a power of $2$. $\endgroup$
    – anon
    Jan 28, 2013 at 8:10
  • 1
    $\begingroup$ @TylerHilton Every positive integer can be expressed as a power of 2 times an odd number. There is a law $(a^b)^c = a^(b \times c)$. Take any positive integer n. Now, $2^n + 1$ can be expressed as $(2^b)^c + 1$ where $b$ is a power of 2 and $c$ is an odd number. Since $c$ is odd, $(2^b) + 1$ is a factor of $(2^b)^c + 1$. $\endgroup$
    – Timothy
    Apr 4, 2020 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .