## anonymous 3 years ago Show that if $2^{m}+1$ is prime then $m=2^{n}$ $n \in \mathbb{N}$ Guidance: $m=r*2^{n}$ So I've started like this: $2^{m}+1=2^{r*2^{n}} +1 = \left( 2^{2^{n}} \right)^{r}+1$ I assume that's a somewhat correct beginning but how do I continue?

1. anonymous

I would really appreciate some help :) @hba @ganeshie8 @ghazi

2. anonymous

have you shown why m has to be a multiple of $$2^n$$?

3. anonymous

No, not really

4. anonymous

That was just the information I got from the start

5. anonymous

yup, don't you feel strange that m has to be a multiple of 2 to start with? the question seems to apply for all $$2^m +1$$ is prime statements.

6. anonymous

Well kind of but i guess the idea is to show the fermat primes by construction the fermat number with the mulitiple of r

7. anonymous

ah. So the question immediately assumes that this is not a proof of fermat primes and instead is asking to proof r=1? lol

8. anonymous

$r=1\rightarrow 2^{2^{n}}+1 | (2^{2^{n}})^{r}+1$ $r=odd \ge 1 \rightarrow 2^{2^{n}}+1 | (2^{2^{n}})^{r}+1$ The second one should be " does not divide" The conlusion is that the trivial dividor is r=1

9. anonymous

To me it doesn't make much sense though :/

10. anonymous

the second one will be out as there is no integer resulting from dividing $$2^{2n} +1$$and $$2^{2nr} +1$$ as the number is prime. r=even case is trivial as if r=even, then it's in $$2^n$$

11. anonymous

Oh I think I understand, so since the number is prime it can't divide which shows us that the assumption in the beginning statement is correct, that if 2^m+1 is prime then m=2^n, am I right?

12. anonymous

One more thing, how do I know that r should be odd?

13. anonymous

well, since it's $$2^{2nr}$$, r cannot be even as that would still mean $$2^{2n}$$ so it should be odd

14. anonymous

Ok, I see that you're writing 2^(2n) and it's 2^(2^n), just a writing error or is the explanation you've made based on 2^(2n) ?

15. anonymous

writing error lol if r is even, then it will either revert to case one or case two. e.g. r=6 will revert to case two and r=8 will revert to case one.

16. anonymous

it m is not a power of two, it contains at least one factor other than 2 or an odd factor

17. anonymous

we also know that $x^n+1$ is always factorable for positive odd integers n.

18. anonymous

one root of $\large x^n+1$ for odd n is $\large x=-1$ hence a factor $\large x+1$ thus $\large x^n+1=(x+1)(x^{n-1}-x^{n-2}+...-x+1)$ or $\large x^n+1$ is not prime

19. anonymous

we conclude that the only possibility that $\huge2^m+1$ to be prime is that m does not contain an odd factor, or that $\huge m=2^n$

20. anonymous

@frx the proof is by contradiction

21. anonymous

I think i understand it

22. anonymous

I have the solution now so I need to sit down and learn the procedure.

23. anonymous

Thank you sirm3d :)

24. anonymous

one warning, though. even if m=2^n there is no guarantee that 2^m + 1 is prime. What the problem asserts is that 2^m + 1 is ALWAYS composite if m contains a factor other than 2.

25. anonymous

That I know, the only primes known are those produced by n=0,1,2,3,4 for 5<=n<=32 the numbers are all composite :)