

A023394


Prime factors of Fermat numbers.


19



3, 5, 17, 257, 641, 65537, 114689, 274177, 319489, 974849, 2424833, 6700417, 13631489, 26017793, 45592577, 63766529, 167772161, 825753601, 1214251009, 6487031809, 70525124609, 190274191361, 646730219521, 2710954639361, 2748779069441, 4485296422913, 6597069766657
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Is it true that this sequence consists of the odd primes p with 2^(2^p) == 1 (mod p)? (David Wilson, Jul 31 2008). Answer from Max Alekseyev: Yes! 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 > m+1. Squaring the last congruence p(m+1) times, we get 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 just before the first 1 we must see 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.
Also primes p such that the multiplicative order of 2 (mod p) is a power of 2. A theorem of Lucas states that if m>1 and prime p divides 1+2^2^m (the mth Fermat number), then p = 1+k*2^(m+2) for some integer k.  T. D. Noe, Jan 29 2009
Wilfrid Keller analyzed the current status of the search for prime factors of Fermat number and stated that all prime factors less than 10^19 are now known. He sent me terms a(25) to a(50).  T. D. Noe, Feb 01 2009, Feb 03 2009, Jan 14 2013
Křížek, Luca, & Somer (2002) show that the sum of the reciprocals of this sequence converge, answering a question of Golomb (1955).  Charles R Greathouse IV, Jul 15 2013


REFERENCES

M. Křížek F. Luca, and L. Somer, 17 Lectures on Fermat Numbers, SpringerVerlag NY 2001.


LINKS

T. D. Noe, Table of n, a(n) for n = 1..50 (from Wilfrid Keller)
Wilfrid Keller, Prime factors k.2^n + 1 of Fermat numbers F_m
M. Křížek, F. Luca, and L. Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97 (2002), pp. 95112.
A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 64 (1995), 1357.
R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC2012) and another new proof, arXiv preprint arXiv:1202.3670, 2012  From N. J. A. Sloane, Jun 13 2012
R. Munafo, Prime Factors of Fermat Numbers


FORMULA

a(n) is a prime factor of the Fermat number 1+2^2^A023395(n).  T. D. Noe, Feb 01 2009
a(n) >> n^2 log^2 n, see Křížek, Luca, & Somer.  Charles R Greathouse IV, Jul 16 2013


MATHEMATICA

Select[Prime[Range[100000]], IntegerQ[Log[2, MultiplicativeOrder[2, # ]]]&] (* T. D. Noe, Jan 29 2009 *)


PROG

(PARI) is(p)=p>2 && Mod(2, p)^lift(Mod(2, znorder(Mod(2, p)))^p)==1 && isprime(p) \\ Charles R Greathouse IV, Feb 04 2013


CROSSREFS

Cf. A000215. Superset of A229851.
Sequence in context: A056826 A272060 A058910 * A176689 A256510 A260377
Adjacent sequences: A023391 A023392 A023393 * A023395 A023396 A023397


KEYWORD

nonn


AUTHOR

David W. Wilson


STATUS

approved



