Why is 2^prime -1 a prime?

Discussion in 'General Math' started by daniel.w.gelder, Feb 27, 2007.

  1. I've tried:

    2^n - 1

    for a lot of N. Prime N always makes a prime, nonprime N always makes
    a nonprime. It's interesting but before I start examining the factors
    that I get I'd like to ask for a simple explanation.

    Thanks
    Dan
     
    daniel.w.gelder, Feb 27, 2007
    #1
    1. Advertisements

  2. daniel.w.gelder

    bert Guest

    2^11 - 1 = 2047 = 23 * 89.

    Part 1 of the simple explanation is that 2^(a*b) - 1
    is always composite, because it has the algebraic
    factors 2^a - 1 and 2^b - 1, and usually more factors.

    Part 2 of the simple explanation is that if p is
    prime, and 2^p - 1 is composite, its factors MUST be
    of the form n*p + 1 (as in 2^11 - 1, above). This
    is a consequence of Fermat's Little Theorem. For
    smallish p, there are seldom enough possible factors.
    --
     
    bert, Feb 27, 2007
    #2
    1. Advertisements

  3. Please define "a lot of N". 2^p-1 is composite for p =
    11,23,29,37,41,43,47,53,59,67,71,73,79,83,97,101,103,....
    etc. etc.

    This assertion is false.

    (1) Please be careful about notation. n != N.
    (2) Although we still do not have a rigorous proof (there are various
    heuristics),
    2^p - 1 will be composite for almost *all* prime numbers p.
    2^p-1 will be prime
    *very* rarely. We do know that for p up to about 33 million,
    2^p-1 is prime only
    44 times. The ratio: #{p < N; 2^p-1 is prime}/#{p < N; p
    prime} goes to 0 as
    N --> oo

    This is trivial high school algebra. Consider the polynomial
    x^(ab) - 1.
    It is divisible by x^a-1 and x^b-1. Now take x = 2.
     
    Pubkeybreaker, Feb 27, 2007
    #3
  4. This is trivial high school algebra. Consider the polynomial
    I figured there would be some of that. Thanks!
     
    daniel.w.gelder, Feb 27, 2007
    #4
  5. daniel.w.gelder

    Prai Jei Guest

    (or somebody else of the same name) wrote thusly
    Well no, there are 40 or so known "good" values of N.

    As Euclid showed, these link directly to the perfect numbers: where 2^n-1 is
    prime, (4^n-2^n)/2 is perfect.
     
    Prai Jei, Mar 2, 2007
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.