20140927, 03:02  #1 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9488_{10} Posts 
"Divides Phi" category
This is an interesting category, and Keller, Broadhurst and others submitted many such primes. The test for it is implemented in the old Y.Gallot's Proth.exe (the newest executable is >10 years old but it runs; its SSE2 code emits an error on modern CPUs, so this can be disabled in 'Options').
Because there is no detailed page for the properties of such numbers, I took a sheet of paper and sat for an hour pondering. Ok, what do we know? 1. Candidates can be primes p = 2q^n+1 with prime q. 2. q ≡ 11 (mod 12) is a well known requirement. (Proof is left to the reader. :winkwink: ... Seriously though, there probably exists a paper from Keller and probably as early as from 70s) 3. n is odd. 4. , so we need 2^q^n ≡ 1 (mod p) but 2^q^{n1} 1 (mod p) UTM database carries some more exotic examples: with k>2 (then q is not restricted to 11 (mod 12) and n is not only odd) or with k*q^n+1  Phi(q^m,2), where m != n. This category sieves well with sr1sieve (cannot combine multiple bases into one workunit for sr2sieve) and tests with LLR. Final check can be done with the old Proth.exe or with modified LLR (with 2^q 1 (mod p) added test). _____________________ 2 · 10859^87905 + 1 and 2 · 11171^100961+1 are found and are under final check with Proth.exe (this is quite slow)... Both checks finished: both divide Phi(q^n,2). Last fiddled with by Batalov on 20140927 at 17:54 Reason: some fluff removed 
20140927, 17:53  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{4}×593 Posts 
Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes.
These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday. Last fiddled with by Batalov on 20140927 at 18:29 Reason: fixed a typo (in the quoted message) 
20140927, 20:45  #3 
Sep 2002
Database er0rr
2^{2}·3·313 Posts 
http://primes.utm.edu/primes/page.php?id=118560 does not appear on http://primes.utm.edu/top20/page.php?id=37
EDIT: it does now. C.C. was away for a day. Last fiddled with by Batalov on 20140929 at 17:28 Reason: (official comment was updated) 
20140927, 21:04  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{4}×593 Posts 
All of these initial labels get manually promoted by C. "The Prime Mogul " C.
Or 'demoted' as the case may be for "Divides xGF(n,a,b)!!!!" that get automatically submitted by the PrimeGrid's engine. It's the weekend. P.S. There's another one! 
20140927, 21:15  #5  
Sep 2002
Database er0rr
2^{2}×3×313 Posts 
Quote:


20140927, 21:53  #6  
Jun 2003
2×7×113 Posts 
Quote:
Also there used to be a project to search 2*a^a+1....everything under 40k was tested. 

20140928, 01:52  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{4}×593 Posts 

20140928, 06:29  #8 
Sep 2002
Database er0rr
2^{2}×3×313 Posts 
Congrats again, this time for 681817 digits

20141003, 19:32  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{4}×593 Posts 
the orderof2 (mod p) test
I have modded LLR to run a naively refactored orderof2mod p test instead of Proth.exe (and even though naive, this is a fast solution; as fast as the primality test, 12 hr max; this is what I used for the current top1 and top3; Proth.exe would have taken cpudays).
I've scanned all known 155 current and former "Divides Phi" categorized Proth primes and they, of course, all confirmed. After that validity test, I moved on to the untagged prime and composite base q Proth numbers (Proth.exe does not run the orderof2 test on them), and found half a dozen interesting divisors. The largest of them is Ian's CRUS S695 prime with k=2, and it was large enough to enter the top20. While the initial identification of such numbers is routine (we can check that 2^(q^n) ≡ 1 (mod k*q^n+1)), the determination of exact Phi() that they divide is more cumbersome than with prime q's. One has to divide away all prime factors of q separately and together until 2^(q^n/factors) !≡ 1. For this particular number, 695 = 5 * 139 and while 2^(q^n/139) already !≡ 1, 2^(q^n/5^k) ≡ 1 for 0<=k<=4 and not for k=5. Hence, as reported, "Divides Phi(695^94625/5^4,2)". 
20141010, 15:34  #10 
Sep 2002
Database er0rr
2^{2}×3×313 Posts 
Congrats yet again, this time for a megaprime: 2 * 59^608685 + 1
Last fiddled with by paulunderwood on 20141010 at 15:34 
20141010, 18:25  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{4}×593 Posts 
Thanks.
Of course a prime q=383, 647, 947 or 67607 (no known primes) would have been so much nicer, but after quite a bit of time spent on them nothing yet was found. So, a small fishing expedition was sent out to small q's  even though they have known primes, they are much faster (this is a short version of a long story; 67607, unfortunately is "generic FFT" only, which is very significantly slower). 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any fast paths out of Category 3 purgatory  NookieN  PrimeNet  9  20180618 19:14 
Option to prefer higher category work?  Runtime Error  PrimeNet  4  20180107 20:20 
646730219521 Divides F19  Buckle  Factoring  7  20100329 22:56 
p^n  1 divides p^m  1 ==> n divides m  jinydu  Homework Help  10  20080806 19:17 