|
| |
|
|
A023394
|
|
Prime factors of Fermat numbers.
|
|
40
|
|
|
|
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 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 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
|
|
|
REFERENCES
|
Michal Krížek, Florian Luca and Lawrence Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) is a prime factor of the Fermat number 1+2^2^A023395(n). - T. D. Noe, Feb 01 2009
|
|
|
MAPLE
|
q:=p->(isprime(p) and irem(2^(2^padic:-ordp(p-1, 2))-1, p) = 0):
|
|
|
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
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
