# Why is 2^prime -1 a prime?

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

1. ### daniel.w.gelderGuest

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

2. ### bertGuest

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

3. ### PubkeybreakerGuest

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.

(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
4. ### daniel.w.gelderGuest

This is trivial high school algebra. Consider the polynomial
I figured there would be some of that. Thanks!

daniel.w.gelder, Feb 27, 2007
5. ### Prai JeiGuest

(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