Proving the Primality of (2^n)+1: A Number Theory Question

[miren324]

I need help. I'm trying to prove that if (2^n)+1 is prime, then there exists an integer k>=0 such that n=2^k.

If n is odd, then (2^n)+1=(2^(2k+1))-(-1)^(2k+1)=(2+1)(stuff...)=(3)(stuff) so it's not prime, a contradiction. So I've knocked out half of the possible n's.

What I'm struggling with is where to go from here. Usually these problems go down the road of proving it doesn't work for all integers EXCEPT the ones I want it to work for. The problem is, I don't know how to divide even integers into two groups: those of the form 2^k and those not of the form 2^k. I don't know what integers such as 6, 10, 12, 14, 18, 20, 22, 24, 26, 28, 30, 34, 36, ... have in common so that I can use some trickery to show that, if n is one of those, 2^n+1 is no longer prime. My first thought was non-perfect powers, but 36=6^2 which cannot be put in the form 2^k.

Any help would be greatly appreciated here. If I've started wrong, as in there's another way to go about this proof that I'm missing, then let me know please.

Thanks.

 

[Mandeep Deka]

There is a beautiful proof to the problem. I just aint able to write it down over here, but go through the book, 'Elementary Number theory' by David M Burton. Its given over there!

 

[uart]

I need help. I'm trying to prove that if (2^n)+1 is prime, then there exists an integer k>=0 such that n=2^k.

I think I can extend your start into an iterative proof.

(first step is just tidying up the first case you proved)

If k is odd then $x^k + 1$ has a zero at $x=-1$ and hence, by the factor theorem, a factor of $(x+1)$.

By the above if $k_0$ is odd then $2^{k_0} + 1$ has a factor of three (2+1). So if $2^{k_0} + 1$ is prime then either $k_0=1$ or $k_0$ is even.

(now extending iteratively)

If $k_0$ is even then write $k_0 = 2 k_1$. Then $4^{k_1} + 1$ is prime, but once again if $k_1$ is odd then by the factor theorem $4^{k_1} + 1$ has a factor of five (4 +1). So either $k_1=1$ or $k_1$ is even.

If $k_1$ is even then write $k_1 = 2 k_2$ (hence [tex]k_0 = 4 k_2[/itex]). Then $16^{k_2} + 1 =$ is prime, but once again ... etc

 

[miren324]

@Mandeep Deka: I have that book. Do you know where in the book this problem is? I don't remember seeing it, but of course I didn't look at every problem in the whole book.

 

[uart]

Hi miren324, did you follow my (outline of a) proof?

 

[Mandeep Deka]

Actually right now i don't have the book, so i don't remember where it is...
But if i not wrong it must have been in the chapter related to perfect numbers.. Just check!