{"id":717,"date":"2022-09-04T21:40:59","date_gmt":"2022-09-05T02:40:59","guid":{"rendered":"http:\/\/csic.som.emory.edu\/~lzhou\/blogs\/?p=717"},"modified":"2022-09-04T21:45:40","modified_gmt":"2022-09-05T02:45:40","slug":"31681130-3445781-1-is-prime","status":"publish","type":"post","link":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/?p=717","title":{"rendered":"3^1681130 + 3^445781 + 1 is prime."},"content":{"rendered":"\n

<\/p>\n\n\n\n

Proof file: <\/p>\n\n\n\nHERE<\/a>\n\n\n\nRecord page here<\/a>.\n\n\n\n

3^1681130+3^445781+1 has 802,104 digits<\/p>\n\n\n\n

factor of p-1:<\/p>\n\n\n\n

3^1681130+3^445781 = 3^445781*(3^1235349+1)<\/p>\n\n\n\n

for 3^1235349+1:<\/p>\n\n\n\n

Divisor of 1235349: {1, 3, 9, 317, 433, 951, 1299, 2853, 3897, 137261, 411783, 1235349}<\/p>\n\n\n\n

for which Cyclotomic[2x,3] divides 3^1235349+1, 3^1235349+1=Product of Phi[2m,3], m is in the above divisor list.<\/p>\n\n\n\n

Phi: Cyclotomic function in Mathematica.<\/p>\n\n\n\n

Phi[2,3] = 4 = 2^2 <\/p>\n\n\n\n

Phi[6,3] = 7 <\/p>\n\n\n\n

Phi[18,3] = 703 = 19*37<\/p>\n\n\n\n

Phi[634,3] = 4419546979734297356356282440566337101076156046659615868982274149497888767412192670918210853094818317044028461371947192040491503227984348283966155849541 = 76824655095930309016347566008213507 *
57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863<\/p>\n\n\n\n

Phi[866,3] = 98049030167138868235272337490364772443278341679136020523778017973332584069900487425071613559614188734321215787769494533118401761096043098454024530209394531738061292786842020371958081509924820005117783644881 = 5197 * 25981 * 10986786121 * 2545641110123181683038777028652229 * 4078872265954752990198205964113561121059 * 48719802170502964448205757292294067215837963275487416471 * 130653562236213178463808841348368553389712956028240802263033 <\/p>\n\n\n\n

Phi[1902,3] = 454579 * 36324397 * 4242031875148351 * 110636908354198084399 * 549512115983126575855924649876601277813687417 * cp_1681130_+3_445781_c1_+1_P1902_c209[ecm50]<\/p>\n\n\n\n

Phi[2598,3] = 49363 * 69183924850105534244247847 * 590120330956087803199 * 24518336107758964004567688595327267 * 72294725439409852600619119163684989 *
cp_1681130_+3_445781_c1_+1_P2598_c292[ecm40]<\/p>\n\n\n\n

Phi[5706,3] = 958609 * 1061317 * 105429763 * 65641802577791850271 * 466581320825998331248111 * 161770166547973894056628560367 <\/em>* 4121313630402929050856881 * 35041165225208415265755372540106879 * 145166850946125723698625301282936985977 *
cp_1681130_+3_445781_c1_+1_P5706_c715[ecm40]<\/p>\n\n\n\n

Phi[7794,3] = 2369645352847 * 18271583019418565050835779232047 *
cp_1681130_+3_445781_c1_+1_P7794_c1194[ecm40]<\/p>\n\n\n\n

Phi[274522,3] = cp_1681130_+3_445781_c1_+1_P274522_c65133[ecm30 – done 20220828]
Phi[823566,3] = 48031581409153 * cp_1681130_+3_445781_c1_+1_P823566_c130252[ecm20]<\/p>\n\n\n\n

Phi[2470698,3] = 59296753 * 2841667923519757 * cp_1681130_+3_445781_c1_+1_P2470698_c390774[ecmpm]<\/p>\n\n\n\n

Factors of p-1:
2^2
3^445781
7
19
37
5197
25981
49363
454579
958609
1061317
36324397
59296753
105429763
10986786121
2369645352847
48031581409153
2841667923519757
4242031875148351
65641802577791850271<\/p>\n\n\n\n

110636908354198084399
590120330956087803199
466581320825998331248111
4121313630402929050856881
69183924850105534244247847
161770166547973894056628560367
18271583019418565050835779232047
2545641110123181683038777028652229
24518336107758964004567688595327267
35041165225208415265755372540106879
72294725439409852600619119163684989
76824655095930309016347566008213507
145166850946125723698625301282936985977
4078872265954752990198205964113561121059
549512115983126575855924649876601277813687417
48719802170502964448205757292294067215837963275487416471
130653562236213178463808841348368553389712956028240802263033
57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863<\/p>\n\n\n\n

Factors of p-1: [2^23^445781<\/em>*7*19<\/em>*37*5197<\/em>*25981*49363<\/em>*454579*958609<\/em>*1061317*36324397*<\/em>59296753*105429763<\/em>*10986786121*2369645352847<\/em>*48031581409153*2841667923519757<\/em>*4242031875148351*65641802577791850271*<\/em>110636908354198084399*590120330956087803199*<\/em>466581320825998331248111*4121313630402929050856881*<\/em>69183924850105534244247847*161770166547973894056628560367*<\/em>18271583019418565050835779232047*2545641110123181683038777028652229<\/em>*24518336107758964004567688595327267*35041165225208415265755372540106879<\/em>*72294725439409852600619119163684989*76824655095930309016347566008213507<\/em>*145166850946125723698625301282936985977*4078872265954752990198205964113561121059<\/em>*549512115983126575855924649876601277813687417*48719802170502964448205757292294067215837963275487416471<\/em>*130653562236213178463808841348368553389712956028240802263033*57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863]<\/p>\n\n\n\n

$ .\/pfgw -tc -k -h”cp_1681130_+3_445781_c1_+1.helper” cp_1681130_+3_445781_c1_+1
Primality testing 3^1681130+3^445781+1 [N-1\/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file cp_1681130_+3_445781_c1_+1.helper
Running N-1 test using base 2
Running N+1 test using discriminant 5, base 5+sqrt(5)
3^1681130+3^445781+1 is Fermat and Lucas PRP! (72918.0430s+0.0527s)<\/p>\n\n\n\n

$ gp
Reading GPRC: \/etc\/gprc \u2026Done.<\/p>\n\n\n\n

                                                                                      GP\/PARI CALCULATOR Version 2.11.3 (released)\n                                                                              amd64 running linux (x86-64\/GMP-6.1.2 kernel) 64-bit version\n                                                                        compiled: Apr  6 2020, gcc version 8.3.1 20190507 (Red Hat 8.3.1-4) (GCC)\n                                                                                                threading engine: single\n                                                                                     (readline v7.0 enabled, extended help enabled)\n\n                                                                                         Copyright (C) 2000-2018 The PARI Group<\/code><\/pre>\n\n\n\n
PARI\/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.<\/p>\n\n\n\n
Type ? for help, \\q to quit.
Type ?17 for how to get moral (and possibly technical) support.<\/p>\n\n\n\n
parisize = 8000000, primelimit = 500000
? \\r CHG.GP
*** Warning: new stack size = 17179869184 (16384.000 Mbytes).
realprecision = 350003 significant digits (350000 digits displayed)<\/p>\n\n\n\n
Welcome to the CHG primality prover!<\/h2>\n\n\n\n
Input file is: cp_1681130_+3_445781_c1_+1.in
Certificate file is: cp_1681130_+3_445781_c1_+1.out
Found values of n, F and G.
Number to be tested has 802103 digits.
Modulus has 213408 digits.
Modulus is 26.605944113118165830% of n.<\/p>\n\n\n\n
NOTICE: This program assumes that n has passed
a BLS PRP-test with n, F, and G as given. If
not, then any results will be invalid!<\/p>\n\n\n\n
Square test passed for F >> G. Using modified right endpoint.<\/p>\n\n\n\n
Search for factors congruent to 1.
Running CHG with h = 16, u = 7. Right endpoint has 161883 digits.
Done! Time elapsed: 810732137ms.
Running CHG with h = 16, u = 7. Right endpoint has 155873 digits.
Done! Time elapsed: 825907227ms.
Running CHG with h = 15, u = 6. Right endpoint has 149984 digits.
Done! Time elapsed: 367063741ms.
Running CHG with h = 15, u = 6. Right endpoint has 141864 digits.
Done! Time elapsed: 403218994ms.
Running CHG with h = 13, u = 5. Right endpoint has 135499 digits.
Done! Time elapsed: 167649019ms.
Running CHG with h = 13, u = 5. Right endpoint has 126589 digits.
Done! Time elapsed: 166344631ms.
Running CHG with h = 11, u = 4. Right endpoint has 115818 digits.
Done! Time elapsed: 62966916ms.
Running CHG with h = 9, u = 3. Right endpoint has 102257 digits.
Done! Time elapsed: 21474045ms.
Running CHG with h = 9, u = 3. Right endpoint has 86036 digits.
Done! Time elapsed: 18674057ms.
Running CHG with h = 7, u = 2. Right endpoint has 57119 digits.
Done! Time elapsed: 4457878ms.
A certificate has been saved to the file: cp_1681130_+3_445781_c1_+1.out<\/p>\n\n\n\n
Running David Broadhurst’s verifier on the saved certificate\u2026<\/p>\n\n\n\n
Testing a PRP called “cp_1681130_+3_445781_c1_+1.in”.<\/p>\n\n\n\n
Pol[1, 1] with [h, u]=[7, 2] has ratio=3.292364120998444652 E-98758 at X, ratio=3.718585580771175970 E-194048 at Y, witness=2.
Pol[2, 1] with [h, u]=[9, 3] has ratio=6.126565950304076461 E-9475 at X, ratio=1.1209288730275909543 E-86752 at Y, witness=2.
Pol[3, 1] with [h, u]=[9, 3] has ratio=4.686378714776338379 E-48664 at X, ratio=4.686378714776338379 E-48664 at Y, witness=2.
Pol[4, 1] with [h, u]=[11, 4] has ratio=1.1328882856917741933 E-83833 at X, ratio=4.446338007106078208 E-54243 at Y, witness=2.
Pol[5, 1] with [h, u]=[10, 5] has ratio=1.3491587713343525002 E-21542 at X, ratio=2.1142563956459774573 E-53855 at Y, witness=2.
Pol[6, 1] with [h, u]=[10, 5] has ratio=2.1142563956459774573 E-53855 at X, ratio=7.365995469140945291 E-44554 at Y, witness=2.
Pol[7, 1] with [h, u]=[15, 6] has ratio=2.101399014710577216 E-89107 at X, ratio=2.654191320795251087 E-38189 at Y, witness=2.
Pol[8, 1] with [h, u]=[13, 6] has ratio=3.530699982729085833 E-8120 at X, ratio=1.9371573230603122010 E-48717 at Y, witness=2.
Pol[9, 1] with [h, u]=[16, 7] has ratio=5.410890206996781797 E-22058 at X, ratio=1.0071182035514125678 E-41222 at Y, witness=2.
Pol[10, 1] with [h, u]=[16, 7] has ratio=5.814090534021862076 E-14617 at X, ratio=8.275867222128713413 E-42071 at Y, witness=2.<\/p>\n\n\n\n
Validated in 116 sec.<\/p>\n\n\n\n
Congratulations! n is prime!
Goodbye!<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Proof file: HERE Record page here. 3^1681130+3^445781+1 has 802,104 digits factor of p-1: 3^1681130+3^445781 = 3^445781*(3^1235349+1) for 3^1235349+1: Divisor of 1235349: {1, 3, 9, 317, 433, 951, 1299, 2853, 3897, 137261, 411783, 1235349} for which Cyclotomic[2x,3] divides 3^1235349+1, 3^1235349+1=Product of Phi[2m,3], m is in the above divisor list. Phi: Cyclotomic function in Mathematica. Phi[2,3] = […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,6],"tags":[],"class_list":["post-717","post","type-post","status-publish","format-standard","hentry","category-to-entertain-myself","category-looking-for-a-megaprime","post-blog"],"_links":{"self":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/717","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=717"}],"version-history":[{"count":3,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/717\/revisions"}],"predecessor-version":[{"id":722,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/717\/revisions\/722"}],"wp:attachment":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=717"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=717"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=717"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}