Author 
Message 

Can these only be found via PPS LLR? 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 1,967

Can these only be found via PPS LLR?
Any Proth number can be a Fermat divisor. (k * 2 ^ n + 1)
SGS no.
Woodall no.
GFN no.
321 some yes, some no.
TRP no.
GCW no.
SR5 no.
Cullen yes.
ESP yes.
PSP yes.
SoB yes.
PPSE yes
PPS yes
PPSMEGA yes.
____________
My lucky number is 75898^{524288}+1 



Thank you Michael! 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

GFN no.
25 · 2^{2141884} + 1 divides F_{2141872} and is a generalized Fermat number.



Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 1,967

GFN no.
25 · 2^{2141884} + 1 divides F_{2141872} and is a generalized Fermat number.
"GFN" meaning our GFN projects.
____________
My lucky number is 75898^{524288}+1 



Can these only be found via PPS LLR?
Any Proth number can be a Fermat divisor. (k * 2 ^ n + 1)
And if the number k*2^n + 1 is a divisor of a Fermat number, say F(m), then the index m satisfies:
m ≤ n2
For generalized Fermat numbers GF(m, b) and xGF(m, b, a) we can only say
m ≤ n1
Note that the number k*2^n + 1 is not necessarily a Proth number in the strict sense that 2^n > k. For example the four factors of F(10) = 2^1024 + 1 are:
11131*2^12 + 1
395937*2^14 + 1
1137640572563481089664199400165229051*2^12 + 1
15922836231138695035093355565980212884107486675001451682970617160257863311947248971452664548043591906237644522563833477152239872181860196421948439690685317315553051258143326480945577516888976026564843006895573500498133825643594092555886322403200003*2^13 + 1
and none of them are Proth primes in the strict sense.
/JeppeSN 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

GFN no.
25 · 2^{2141884} + 1 divides F_{2141872} and is a generalized Fermat number.
"GFN" meaning our GFN projects.
A GFN can divide a Fermat number.
1059094^{1048576} + 1 may be the largest known Fermat divisor (with a probability of (2/1059094)^{1048576}).




GFN no.
25 · 2^{2141884} + 1 divides F_{2141872} and is a generalized Fermat number.
"GFN" meaning our GFN projects.
Let me take a recent GFN16 project find as an example, namely the prime:
53942572^65536 + 1
To see this in the Proth form, we would need to split the base 53942572 into a power of two and an odd number. It goes like this 53942572 = 13485643*2^2 and so the GFN16 prime can be written:
13485643^65536*(2^2)^65536 + 1
or:
(13485643^65536)*2^131072 + 1
So this is of the "Proth" form k*2^n + 1 where n=131072 and k is the enormous odd number 13485643^65536. So given the form, it could divide some F(m) with m ≤ 131070. However, since k is so incredibly huge, there is no need of checking it, the chance is too slim.
If we found a GFN16 prime b^65536+1 with the special property that b is a really small odd number times a big power of two, the chances would be a little bit better. Say, if 25165824^65536+1 were prime (I have not checked, so it probably is not), then 25165824 = 3*2^23, and we would end up with "Proth" form:
3^65536*(2^23)^65536 + 1
or:
(3^65536)*2^1507328 + 1
but even in this extreme case, the size of k (= 3^65536) is so big that it is not worth the computation time to check if it is a Fermat divisor.
/JeppeSN




Similar remarks apply to GCW primes of the generalized Cullen form if the base is even, such as:
1323365*116^1323365 + 1 (Scott Brown, January 2018)
which could in principle be a Fermat divisor, but it is a waste of effort to check for it.
/JeppeSN 



Shorter put, I agree with Yves.
Note that his example 25*2^2141884 + 1 was found by "our" PPS LLR search, and was originally on the GFN Top 20.
/JeppeSN 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Robish just asked me if there is a software he could use to check if 1059094^{1048576} + 1 is the divisor of a Fermat number.
I was thinking of modifying genefer for this purpose but I think that we can do better.
If P is prime then 2^{P1} = 1 (mod P).
But x^{n}1 = Prod_{dn} Phi_{d}(x), where Phi_{d} is the d^{th} cyclotomic polynomial.
Then P = 1059094^{1048576} + 1 divides at least one "cyclotomic number" Phi_{d}(2) where d is a divisor of 1059094^{1048576}.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2^{h} * 529547^{k} with 0 <= h, k <= 1048576.
We have Phi_{d}(x) = Phi_{b}(x^{d/b}) and Phi_{b}(x) = Phi_{b/2}(x).
Then we can compute the numbers Phi_{d}(2) modulo P and check if the result is zero.
This can be applied to 10223*2^{31172165}+1 or 3*2^{10829346}+1. They divide a huge cyclotomic number.
A small example: P = 6^{4}+1 is prime. P divides Phi_{648}(2) = 2^{216}  2^{108} + 1. (6^{4} = 2 * 648)



robishVolunteer moderator Volunteer tester
Send message
Joined: 7 Jan 12 Posts: 2139 ID: 126266 Credit: 6,807,374,603 RAC: 3,177,237

Robish just asked me if there is a software he could use to check if 1059094^{1048576} + 1 is the divisor of a Fermat number.
I was thinking of modifying genefer for this purpose but I think that we can do better.
If P is prime then 2^{P1} = 1 (mod P).
But x^{n}1 = Prod_{dn} Phi_{d}(x), where Phi_{d} is the d^{th} cyclotomic polynomial.
Then P = 1059094^{1048576} + 1 divides at least one "cyclotomic number" Phi_{d}(2) where d is a divisor of 1059094^{1048576}.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2^{h} * 529547^{k} with 0 <= h, k <= 1048576.
We have Phi_{d}(x) = Phi_{b}(x^{d/b}) and Phi_{b}(x) = Phi_{b/2}(x).
Then we can compute the numbers Phi_{d}(2) modulo P and check if the result is zero.
This can be applied to 10223*2^{31172165}+1 or 3*2^{10829346}+1. They divide a huge cyclotomic number.
A small example: P = 6^{4}+1 is prime. P divides Phi_{648}(2) = 2^{216}  2^{108} + 1. (6^{4} = 2 * 648)
Thanks Yves, but I fear that math is beyond me. I'll have to take your word for it :)
____________
My lucky numbers 1059094^{1048576}+1 and 224584605939537911+81292139*23#*n for n=0..26 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Actually, it is easier than I expected.
If p is an odd prime then p divides 2^{p1}  1 (Fermat's little theorem).
Let m be the smallest integer such that p divides 2^{m}  1 (the multiplicative order of 2 modulo p).
It's not difficult to prove that m must divide p1 then if the factorisation of p1 is known, m can be computed.
And we have the theorem:
If p doesn't divide m then
m is the order of a modulo p <=> p divides Phi_m(a) (the m^{th} cyclotomic polynomial).
I can extend genefer with the computation of the multiplicative order of 2 modulo p = b^N+1.
If this order m is a power of 2 then the cyclotomic polynomial is of the form x^(m/2)+1 and p divides a Fermat number.
Otherwise p still divides Phi_m(2) which is also too large to be computed. 

