Browse Groups

• ... have ... divisor ... the ... Cool question!! 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
Message 1 of 3 , Mar 27, 2003
View Source
--- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
> 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
> 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?

Cool question!!

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

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
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.