A023394 Prime factors of Fermat numbers.

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

Offset: 1

Author

David W. Wilson

Keywords

• nonn

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 m-th 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

To test if a prime p is a member, it suffices to check if the multiplicative order of 2 modulo p is a power of two. But it is obvious that the order is a divisor of p-1. Therefore it is enough to test if 2^(2^j) == 1 (mod p) where 2^j is the largest power of two that divides p-1. - Jeppe Stig Nielsen, Mar 13 2022

Primes p such that 2^(2^p) == 2^p - 1 (mod p); i.e., prime numbers in A373580. - Thomas Ordowski, Jun 11 2024

References

• Michal Krížek, Florian Luca and Lawrence Somer, 17 Lectures on Fermat Numbers, Springer-Verlag 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.
• Michal Krížek, Florian Luca and Lawrence Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory, Vol. 97 (2002), pp. 95-112.
• Sourangshu Ghosh and Pranjal Jain, On Fermat Numbers and Munafo's Conjecture, ResearchGate (2021).
• A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp., Vol. 64. No. 203 (1995), 1357.
• Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof (2012), arXiv preprint arXiv:1202.3670 [math.HO], 2012-2018.
• Robert Munafo, Prime Factors of Fermat Numbers.
• Mercedes Orús-Lacort, Fermat numbers are not prime numbers for n >= 5, ResearchGate (2020).
• Lorenzo Sauras-Altuzarra, Some properties of the factors of Fermat numbers, Art Discrete Appl. Math. (2022).

Crossrefs

Supersequence of A229851.

Cf. A000215, A344784.

Programs

Maple

q:=p->(isprime(p) and irem(2^(2^padic:-ordp(p-1, 2))-1, p) = 0):
select(q, [$1..10^5])[]; # Lorenzo Sauras Altuzarra, Feb 20 2023

Mathematica

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

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

PARI

my(isfermatdivisor(m)=if(m>0, if(m==1, return(1), v=valuation(m-1, 2); c=0; if(m>2, e=logint(m-1, 2); if(e==v&&Mod(m-1, e)==0, t=logint(v, 2); c=1)); if(v>6&&c==0, x=2; t=0; for(i=0, v-2, if(x+1==m, c=1; break); s=x*x; x=s-s\m*m; t++)); if(c==1, print((m-1)/2^v"*2^"v" + 1 divides 2^(2^"t") + 1")); return(c)))); L=List([]); forstep(m=3, 63766529, 2, if(isprime(m)&&isfermatdivisor(m), listput(L, m))); print(); print(Vec(L)); \\ Arkadiusz Wesolowski, Jan 16 2018

PARI

forprime(p=2,,Mod(2,p)^(2^valuation(p-1,2))==1&&print1(p,", ")) \\ Jeppe Stig Nielsen, Mar 13 2022

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

Sum_{n>=1} 1/a(n) = A344784. - Amiram Eldar, May 30 2021