Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Kermit Rose
    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
    • 0 Attachment
      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.