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

2^(2^m) + 1 mod prime

Expand Messages
  • Kermit Rose
    2^(2^m) + 1 mod prime 3 cannot divide any number in this series because (2 -1)^2 + 1 = 2 5 cannot divide any number in this series except 5 because (2 -
    Message 1 of 2 , Jul 29, 2007
    • 0 Attachment
      2^(2^m) + 1 mod prime

      3 cannot divide any number in this series because (2 -1)^2 + 1 = 2

      5 cannot divide any number in this series except 5 because (2 - 1)^2 + 1 = 2

      7 cannot divide any number in this series because (5 - 1)^2 + 1 = 3 mod
      7 and (3-1)^2 + 1 = 5

      mod 11 repeats the sequence 5,6,4,10

      mod 13 repeats the sequence 4,10

      17 cannot divide any number in this series because (2 - 1)^2 + 1 = 2

      In general no number in this series divides any other number in the series

      In order for 2^(2^m) + 1 to be divisible by p,

      the equation (x - 1)^2 + 1 = 0 must have a solution mod p.

      (x - 1)^2 + 1 = x^2 - 2 x + 1 + 1 = x^2 - 2x + 2

      x^2 - 2 x + 2 = 0

      x = 1 + i or x = 1 - i

      In order for 2^(2^m) + 1 to be divisible by p, p must be = 1 mod 4.


      In order for 2^(2^m) + 1 to be divisible by p,
      one of the equations

      x^2 - 2x + 2 = 1 + i
      or
      x^2 - 2 x + 2 = 1 - i
      must have a solution mod p

      One of the equations

      x^2 - 2x + 1 - i = 0
      or
      x^2 - 2 x + 1 + i = 0

      must have a solution mod p.

      x1 = 1 + sqrt(i) or x1 = 1 - sqrt(i)

      x2 = 1 + sqrt( -i) or x2 = 1 - sqrt(-i)

      Is it true that if any of these exist, mod p, then all of them exist?


      In mod 641, we may take i = 155, and we may take sqrt(i) = 257.

      In general, which primes, p, divide a number of the form 2(2^m) + 1
      will be related to the existence of

      sqrt(-1), sqrt(sqrt(-1)), sqrt(sqrt(sqrt(-1))) , etc mod p.


      Kermit < kermit@... >
    • Paul Leyland
      ... .. ... This result is (a) well-known and (b) easy to prove. Let F_i = 2^(2^i)+1 where i = 1. Then F_{i+1} = 2^(2^{i+1}) + 1 = (2^(2^{i+1}) - 1) + 2 =
      Message 2 of 2 , Jul 29, 2007
      • 0 Attachment
        On Sun, 2007-07-29 at 13:16, Kermit Rose wrote:
        > 2^(2^m) + 1 mod prime
        ..
        > In general no number in this series divides any other number in the
        > series

        This result is (a) well-known and (b) easy to prove.

        Let F_i = 2^(2^i)+1 where i >= 1.

        Then F_{i+1} = 2^(2^{i+1}) + 1
        = (2^(2^{i+1}) - 1) + 2
        = (2^(2^(i) + 1) * (2^(2^(i) - 1) + 2
        = F_i * (F_i - 2) + 2

        So F_{i+1} == 2 mod F_i

        The general result follows by induction.

        Incidentally, this provides another nice proof of the infinity of the
        primes. No F_n is divisible by any other F_n and n may take on any
        integer value.


        Paul



        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.