Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

frx

  • 2 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?

  • This Question is Closed
  1. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No, not really

  4. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That was just the information I got from the start

  5. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  10. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  13. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  14. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. Shadowys
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  17. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  18. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @frx the proof is by contradiction

  21. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think i understand it

  22. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you sirm3d :)

  24. sirm3d
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  26. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.