Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

johnny0929

  • 3 years ago

If \(2^{n}-1\) is prime, prove that n is prime?

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

    @satellite73

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

    @KingGeorge

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

    Well, suppose towards a contradiction that \(n=a\cdot b\) is composite with \(a,b>1\). Then, \[2^n-1=2^{ab}-1=(2^a)^b-1\]Now substitute \(2^a=x\) to get \(x^b-1\), and use the formula I helped you prove by induction earlier. Make sense?

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

    I understand all the way up to the former formula. I know that it would look like\[(x-1)(x^{b-1}+x^{b-2}+...+x^{2}+x+1)\] but why does that make \(2^{n}-1\) not prime?

  5. KingGeorge
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    \[2^n-1=(2^a)^b-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+...+2^a+1)\]Since \(a>1\), \(2^a-1>1\), and so we have that \((2^a-1)|(2^n-1)\).

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

    thank you so much i understand it now. Proof writing is a very difficult task for me :(

  7. KingGeorge
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Proof writing is definitely an acquired skill :P

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy