PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Fermat Divisor question

Author Message
Profile Jordan Romaidis
Avatar
Send message
Joined: 11 May 17
Posts: 213
ID: 880615
Credit: 659,658,890
RAC: 437,616
Discovered 4 mega primesEliminated 1 conjecture "k"Discovered 1 AP26Found 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 1 prime in the 2020 Tour de Primes Mountain StageFound 1 mega prime in the 2020 Tour de Primes Mountain Stage321 LLR Ruby: Earned 2,000,000 credits (4,574,478)Cullen LLR Ruby: Earned 2,000,000 credits (2,080,460)ESP LLR Gold: Earned 500,000 credits (502,325)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,000,054)PPS LLR Emerald: Earned 50,000,000 credits (90,479,455)PSP LLR Bronze: Earned 10,000 credits (23,710)SoB LLR Sapphire: Earned 20,000,000 credits (39,985,666)SR5 LLR Jade: Earned 10,000,000 credits (16,535,456)SGS LLR Jade: Earned 10,000,000 credits (18,555,210)TRP LLR Gold: Earned 500,000 credits (525,711)Woodall LLR Jade: Earned 10,000,000 credits (15,028,246)321 Sieve Amethyst: Earned 1,000,000 credits (1,062,420)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,606,749)PPS Sieve Sapphire: Earned 20,000,000 credits (23,296,981)AP 26/27 Double Silver: Earned 200,000,000 credits (221,515,970)GFN Double Bronze: Earned 100,000,000 credits (145,999,871)PSA Emerald: Earned 50,000,000 credits (52,891,089)
Message 126970 - Posted: 17 Feb 2019 | 19:16:53 UTC

Can these only be found via PPS LLR?

Profile Michael GoetzProject donor
Honorary cruncher
Avatar
Send message
Joined: 21 Jan 10
Posts: 13211
ID: 53948
Credit: 218,263,846
RAC: 16,877
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (12,843,762)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,004,590)SGS LLR Ruby: Earned 2,000,000 credits (2,276,011)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (9,401,911)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,114,159)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (72,383,585)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 126971 - Posted: 17 Feb 2019 | 19:34:37 UTC - in response to Message 126970.

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
PPS-MEGA yes.

____________
My lucky number is 75898524288+1
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)

Profile Jordan Romaidis
Avatar
Send message
Joined: 11 May 17
Posts: 213
ID: 880615
Credit: 659,658,890
RAC: 437,616
Discovered 4 mega primesEliminated 1 conjecture "k"Discovered 1 AP26Found 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 1 prime in the 2020 Tour de Primes Mountain StageFound 1 mega prime in the 2020 Tour de Primes Mountain Stage321 LLR Ruby: Earned 2,000,000 credits (4,574,478)Cullen LLR Ruby: Earned 2,000,000 credits (2,080,460)ESP LLR Gold: Earned 500,000 credits (502,325)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,000,054)PPS LLR Emerald: Earned 50,000,000 credits (90,479,455)PSP LLR Bronze: Earned 10,000 credits (23,710)SoB LLR Sapphire: Earned 20,000,000 credits (39,985,666)SR5 LLR Jade: Earned 10,000,000 credits (16,535,456)SGS LLR Jade: Earned 10,000,000 credits (18,555,210)TRP LLR Gold: Earned 500,000 credits (525,711)Woodall LLR Jade: Earned 10,000,000 credits (15,028,246)321 Sieve Amethyst: Earned 1,000,000 credits (1,062,420)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,606,749)PPS Sieve Sapphire: Earned 20,000,000 credits (23,296,981)AP 26/27 Double Silver: Earned 200,000,000 credits (221,515,970)GFN Double Bronze: Earned 100,000,000 credits (145,999,871)PSA Emerald: Earned 50,000,000 credits (52,891,089)
Message 126972 - Posted: 17 Feb 2019 | 19:40:27 UTC - in response to Message 126971.

Thank you Michael!

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 126974 - Posted: 17 Feb 2019 | 20:06:47 UTC - in response to Message 126971.

GFN no.

25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.

Profile Michael GoetzProject donor
Honorary cruncher
Avatar
Send message
Joined: 21 Jan 10
Posts: 13211
ID: 53948
Credit: 218,263,846
RAC: 16,877
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (12,843,762)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,004,590)SGS LLR Ruby: Earned 2,000,000 credits (2,276,011)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (9,401,911)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,114,159)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (72,383,585)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 126978 - Posted: 17 Feb 2019 | 21:09:07 UTC - in response to Message 126974.

GFN no.

25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.



"GFN" meaning our GFN projects.
____________
My lucky number is 75898524288+1
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1124
ID: 306875
Credit: 13,752,255
RAC: 21,407
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (4,453,063)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Bronze: Earned 10,000 credits (99,305)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 126983 - Posted: 17 Feb 2019 | 21:29:22 UTC - in response to Message 126971.

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 ≤ n-2

For generalized Fermat numbers GF(m, b) and xGF(m, b, a) we can only say

m ≤ n-1

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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 126988 - Posted: 17 Feb 2019 | 21:50:51 UTC - in response to Message 126978.

GFN no.

25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.

"GFN" meaning our GFN projects.

A GFN can divide a Fermat number.
10590941048576 + 1 may be the largest known Fermat divisor (with a probability of (2/1059094)1048576).

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1124
ID: 306875
Credit: 13,752,255
RAC: 21,407
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (4,453,063)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Bronze: Earned 10,000 credits (99,305)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 126989 - Posted: 17 Feb 2019 | 21:51:05 UTC - in response to Message 126978.

GFN no.

25 · 22141884 + 1 divides F2141872 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

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1124
ID: 306875
Credit: 13,752,255
RAC: 21,407
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (4,453,063)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Bronze: Earned 10,000 credits (99,305)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 126992 - Posted: 17 Feb 2019 | 22:01:33 UTC

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

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1124
ID: 306875
Credit: 13,752,255
RAC: 21,407
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (4,453,063)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Bronze: Earned 10,000 credits (99,305)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 126996 - Posted: 17 Feb 2019 | 22:21:43 UTC

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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 129006 - Posted: 26 Apr 2019 | 11:57:57 UTC

Robish just asked me if there is a software he could use to check if 10590941048576 + 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 2P-1 = 1 (mod P).

But xn-1 = Prodd|n Phid(x), where Phid is the dth cyclotomic polynomial.

Then P = 10590941048576 + 1 divides at least one "cyclotomic number" Phid(2) where d is a divisor of 10590941048576.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2h * 529547k with 0 <= h, k <= 1048576.
We have Phid(x) = Phib(xd/b) and Phib(x) = Phib/2(-x).
Then we can compute the numbers Phid(2) modulo P and check if the result is zero.

This can be applied to 10223*231172165+1 or 3*210829346+1. They divide a huge cyclotomic number.

A small example: P = 64+1 is prime. P divides Phi648(2) = 2216 - 2108 + 1. (64 = 2 * 648)

Profile RobishProject donor
Volunteer moderator
Avatar
Send message
Joined: 7 Jan 12
Posts: 1579
ID: 126266
Credit: 4,080,101,660
RAC: 5,026,368
Discovered the World's First AP27!!!Discovered 9 mega primesDiscovered 1 AP272018 Tour de Primes largest primeFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (7,910,214)Cullen LLR Jade: Earned 10,000,000 credits (13,883,129)ESP LLR Turquoise: Earned 5,000,000 credits (6,404,450)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,466,498)PPS LLR Sapphire: Earned 20,000,000 credits (44,431,866)PSP LLR Turquoise: Earned 5,000,000 credits (7,758,266)SoB LLR Sapphire: Earned 20,000,000 credits (36,149,530)SR5 LLR Turquoise: Earned 5,000,000 credits (8,227,593)SGS LLR Turquoise: Earned 5,000,000 credits (5,177,463)TRP LLR Sapphire: Earned 20,000,000 credits (26,049,674)Woodall LLR Turquoise: Earned 5,000,000 credits (5,062,771)321 Sieve Turquoise: Earned 5,000,000 credits (7,116,748)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,892,369)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,515,338)PPS Sieve Double Gold: Earned 500,000,000 credits (792,454,680)TRP Sieve (suspended) Silver: Earned 100,000 credits (121,416)AP 26/27 Emerald: Earned 50,000,000 credits (87,312,628)GFN Double Ruby: Earned 2,000,000,000 credits (3,012,342,526)
Message 129043 - Posted: 28 Apr 2019 | 9:37:27 UTC - in response to Message 129006.
Last modified: 28 Apr 2019 | 9:39:17 UTC

Robish just asked me if there is a software he could use to check if 10590941048576 + 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 2P-1 = 1 (mod P).

But xn-1 = Prodd|n Phid(x), where Phid is the dth cyclotomic polynomial.

Then P = 10590941048576 + 1 divides at least one "cyclotomic number" Phid(2) where d is a divisor of 10590941048576.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2h * 529547k with 0 <= h, k <= 1048576.
We have Phid(x) = Phib(xd/b) and Phib(x) = Phib/2(-x).
Then we can compute the numbers Phid(2) modulo P and check if the result is zero.

This can be applied to 10223*231172165+1 or 3*210829346+1. They divide a huge cyclotomic number.

A small example: P = 64+1 is prime. P divides Phi648(2) = 2216 - 2108 + 1. (64 = 2 * 648)


Thanks Yves, but I fear that math is beyond me. I'll have to take your word for it :)
____________
My lucky numbers 10590941048576+1 and 181457032297751865536+1

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 129051 - Posted: 28 Apr 2019 | 17:03:40 UTC

Actually, it is easier than I expected.

If p is an odd prime then p divides 2p-1 - 1 (Fermat's little theorem).
Let m be the smallest integer such that p divides 2m - 1 (the multiplicative order of 2 modulo p).
It's not difficult to prove that m must divide p-1 then if the factorisation of p-1 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 mth 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.

Message boards : General discussion : Fermat Divisor question

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.17, 1.14, 1.39
Generated 27 May 2020 | 16:06:50 UTC