## 2^(2^m) + 1 mod prime

Expand Messages
• 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
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@... >
• ... .. ... 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
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.