Question about A023394

[Max Alekseyev]

2008/7/31 David Wilson <dwilson at gambitcomm.com>:
> A023394 ?= {prime p: 2^2^p == 1 (mod p)}
>

This is correct.

If prime p divides Fm = 2^(2^m)+1 then 2^(2^(m+1)) == 1 (mod p) and p
is of the form p = k*2^(m+2)+1 > 2^(m+1).
Taking squares p - 2^(m+1) times, we have got 2^(2^p) == 1 (mod p).

On the other hand, if 2^(2^p) == 1 (mod p) for prime p, consider a
sequence 2^(2^0), 2^(2^1), 2^(2^2), ..., 2^(2^p). Modulo p this
sequence ends with a bunch of 1's but right before first 1 it must
come -1 (as the only other square root of 1 modulo prime p), i.e., for
some m, 2^(2^m) == -1 (mod p), implying that p divides Fermat number
2^(2^m) + 1.

Regards,
Max