## Factoring 2^11 -1 and proving 2^13 -1 to be prime.

Expand Messages
• I just noticed this morning a fact that probably most everyone on this list has know for a long time. If q is prime, and the prime p divides 2^q - 1 then q
Message 1 of 1 , Dec 27, 2006
I just noticed this morning a fact that probably most everyone on this
list has know for a long time.

If q is prime,

and the prime p
divides

2^q - 1

then q divides (p-1).

I used this observation to quickly find the factors of 2^11 -1.

If p divides 2^11 -1, then 11 divides (p - 1).

22 + 1 = 23 is prime and 23 less than square root of 2^11 -1.

So I divide 23 into 2047 to get 89.

23 * 89 = 2047.

I observe by the way that 89 = 11 * 8 + 1

and that there are no other candidates between 23 and square root of
2^11 - 1

for 44 + 1 = 45 is not prime,
and 66 + 1 = 67 fails to be a candidate because 67 is > square root of
(2^11 - 1).

If p divides 2^13 - 1
then 13 divides (p-1).

Candidates for p less than square root of (2^13 - 1)
are

4 * 13 + 1 = 53
and
6 * 13 + 1 = 79.

Neither of these divide (2^13 - 1) .

Therefore 2^13 -1 is prime.
Your message has been successfully submitted and would be delivered to recipients shortly.
»
«