# 3^1681130 + 3^445781 + 1 is prime.

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] = 4 = 2^2

Phi[6,3] = 7

Phi[18,3] = 703 = 19*37

Phi[634,3] = 4419546979734297356356282440566337101076156046659615868982274149497888767412192670918210853094818317044028461371947192040491503227984348283966155849541 = 76824655095930309016347566008213507 *

57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863

Phi[866,3] = 98049030167138868235272337490364772443278341679136020523778017973332584069900487425071613559614188734321215787769494533118401761096043098454024530209394531738061292786842020371958081509924820005117783644881 = 5197 * 25981 * 10986786121 * 2545641110123181683038777028652229 * 4078872265954752990198205964113561121059 * 48719802170502964448205757292294067215837963275487416471 * 130653562236213178463808841348368553389712956028240802263033

Phi[1902,3] = 454579 * 36324397 * 4242031875148351 * 110636908354198084399 * 549512115983126575855924649876601277813687417 * cp_1681130_+3_445781_c1_+1_P1902_c209[ecm50]

Phi[2598,3] = 49363 * 69183924850105534244247847 * 590120330956087803199 * 24518336107758964004567688595327267 * 72294725439409852600619119163684989 *

cp_1681130_+3_445781_c1_+1_P2598_c292[ecm40]

Phi[5706,3] = 958609 * 1061317 * 105429763 * 65641802577791850271 * 466581320825998331248111 * 161770166547973894056628560367* ** 4121313630402929050856881 * 35041165225208415265755372540106879 * 145166850946125723698625301282936985977 *

cp_1681130_+3_445781_c1_+1_P5706_c715[ecm40]

Phi[7794,3] = 2369645352847 * 18271583019418565050835779232047 *

cp_1681130_+3_445781_c1_+1_P7794_c1194[ecm40]

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]

Phi[2470698,3] = 59296753 * 2841667923519757 * cp_1681130_+3_445781_c1_+1_P2470698_c390774[ecmpm]

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

110636908354198084399

590120330956087803199

466581320825998331248111

4121313630402929050856881

69183924850105534244247847

161770166547973894056628560367

18271583019418565050835779232047

2545641110123181683038777028652229

24518336107758964004567688595327267

35041165225208415265755372540106879

72294725439409852600619119163684989

76824655095930309016347566008213507

145166850946125723698625301282936985977

4078872265954752990198205964113561121059

549512115983126575855924649876601277813687417

48719802170502964448205757292294067215837963275487416471

130653562236213178463808841348368553389712956028240802263033

57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863

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**110636908354198084399**590120330956087803199**466581320825998331248111**4121313630402929050856881**69183924850105534244247847**161770166547973894056628560367**18271583019418565050835779232047**2545641110123181683038777028652229**24518336107758964004567688595327267**35041165225208415265755372540106879**72294725439409852600619119163684989**76824655095930309016347566008213507**145166850946125723698625301282936985977**4078872265954752990198205964113561121059**549512115983126575855924649876601277813687417**48719802170502964448205757292294067215837963275487416471**130653562236213178463808841348368553389712956028240802263033*57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863]

$ ./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)

$ gp

Reading GPRC: /etc/gprc …Done.

```
GP/PARI CALCULATOR Version 2.11.3 (released)
amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Apr 6 2020, gcc version 8.3.1 20190507 (Red Hat 8.3.1-4) (GCC)
threading engine: single
(readline v7.0 enabled, extended help enabled)
Copyright (C) 2000-2018 The PARI Group
```

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.

Type ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000

? \r CHG.GP

*** Warning: new stack size = 17179869184 (16384.000 Mbytes).

realprecision = 350003 significant digits (350000 digits displayed)

## Welcome to the CHG primality prover!

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.

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!

Square test passed for F >> G. Using modified right endpoint.

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

Running David Broadhurst’s verifier on the saved certificate…

Testing a PRP called “cp_1681130_+3_445781_c1_+1.in”.

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.

Validated in 116 sec.

Congratulations! n is prime!

Goodbye!