Question

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?

Answer 1

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

Answer 2

have you shown why m has to be a multiple of \(2^n\)?

Answer 3

No, not really

Answer 4

That was just the information I got from the start

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

\[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

Answer 9

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

Answer 10

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\)

Answer 11

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?

Answer 12

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

Answer 13

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

Answer 14

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) ?

Answer 15

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.

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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 \]

Answer 20

@frx the proof is by contradiction

Answer 21

I think i understand it

Answer 22

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

Answer 23

Thank you sirm3d :)

Answer 24

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.

Answer 25

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 :)