A little bird told me that if 2n+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⋅2m for some a not a power of 2 and some integer m. This gives 2n+1=2a⋅2m+1. Now I suspect there’s a way to factor that, but I don’t see how. Can someone give me a hint?
Hint. For any odd natural number a, the polynomial x+1 divides xa+1 evenly.
In particular, we have xa+1x+1=(−x)a−1(−x)−1=1−x+x2−⋯+(−x)a−1 by the geometric sum formula. In this case, specialize to x=22m 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.)