> I was idly looking for Mersenne numbers (2^p-1, p prime) which

have

> many "small" divisors. Of course, it is well known that any

divisor

> of 2^p-1 must be of the form 2*a*p+1, for some integer a. (With

the

> solitary exception that when p==2, 3 divides 2^p-1 -- those damn

Cool question!!

> even primes don't know how to behave...)

>

> A couple of things I noticed, which are true for all p<=10000.

>

> If 2*p+1 divides 2^p-1, either p==3 or p==(11 mod 12).

>

> 4*p+1 never divides 2^p-1.

>

> If 6*p+1 divides 2^p-1, p==(1 mod 4).

>

> If 8*p+1 divides 2^p-1, p==(5 mod 6).

>

> If 10*p+1 divides 2^p-1, p==(7 mod 12).

>

> 12*p+1 never divides 2^p-1.

>

> If 14*p+1 divides 2^p-1, p==(5 mod 12).

>

> If 16*p+1 divides 2^p-1, p==(1 mod 6).

>

> If 18*p+1 divides 2^p-1, p==(3 mod 4).

>

> 20*p+1 never divides 2^p-1.

>

> If 22*p+1 divides 2^p-1, p==(1 mod 12).

>

> If 24*p+1 divides 2^p-1, p==(1 mod 2).

>

>

> And then that same cycle of 12 rules seems to repeat...

>

> Are these results well known? Are they true for all p?

> Does the cycle repeat as it seems to?

Don't you just need to use Fermat's Small Theorem.

1) If 2*p+1 divides 2^p-1

You have a prime p and a prime 2*p+1 -- I assume the divisor is

also a prime number, you don't explicitly say

:. p is 5%6

Consider 2 cases, p is 1%4 and p is 3%4

First let p = 4*n+1

2^p % (2*p+1)

= 2^(4*n+1) % (2*(4*n+1)+1)

= 2^(4*n+1) % (8*n+3)

= Jacobi(2|8*n+3)

= -1

:. 2^p-1 is -2%(2*p+1) and not zero

Second let p = 4*n+3

2^p % (2*p+1)

= 2^(4*n+3) % (2*(4*n+3)+1)

= 2^(4*n+3) % (8*n+7)

= Jacobi(2|8*n+7)

= +1

:. 2^p-1 is 0%(2*p+1)

:. p is 3%4 and 5%6

:. p is 11%12

2) If 4*p+1 divides 2^p-1

You have a prime number p and a prime number 4*p+1 -- again making

that assumption.

Consider p=2n+1

2^p % (4*p+1)

= 2^(2*n+1) % (4*(2*n+1)+1)

= 2^(2*n+1) % (8*n+5)

But 2^(4*n+2) % (8*n+5) = Jacobi(2|8*n+5) = -1

And so (2^(2*n+1))^2 = -1

:. 2^(2*n+1) % (8*n+5) =/= 1

:. 2^p-1 % (4*p+1) =/=0

:. These conditions for p can never be satisfied

3) If 6*p+1 divides 2^p-1

You have a prime number p and a prime number 6*p+1 -- again making

the same assumption.

Consider p=4*n+3

2^p % (6*p+1)

= 2^(4*n+3) % (6*(4*n+3)+1)

= 2^(4*n+3) % (24*n+19)

If this was +1, then

2^(12*n+9) % (24*n+19) = 1^3 = 1

but 2^(12*n+9) % (24*n+19) = Jacobi(2|24*n+19) = -1

Contradiction.

So p has to be 4*n+1

The proof that it can be 4*n+1 is simple - you just gotta find

one! I bet Jack's allready done that.

I assume the rest of the cases can be approached with those same

techniques, so it shouldn't be too hard. That's your homework

Jack!! :)

Ralph