Primality Certificate for (6615^2017-1)/6614

This certificate uses a theorem of Konyagin and Pomerance to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 30.835649% factorization of N-1:

From this partial factorization, we use sufficient of the largest prime factors of N-1 so that their product F is at least N ^3/10 :

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 30.835649%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 53 suffices.

Express N in base F

As F³ < N < F⁴ and N ≡ 1 (mod F), we can let N = c₃·F³ + c₂·F² + c₁·F + 1. Let c₄ = c₃·F+c₂.

• c₁= 95139 8924539069 8251914564 7640961841 3303586714 0489729838 2486762146 3785492246 8639250942 9294593753 9182049191 0376680557 1272414927 7523342381 7928780151 0284573234 1195035568 7274332430 8788342819 9370856060 7587975290 1272826841 2296903248 7566922268 5431537880 9466661366 8954256028 9235039506 2349412846 0449843103 3307349775 2882962614 7862056786 4001288028 5441448862 1758024315 2037473861 5260684853 6166083036 8550219285 0271147926 1227216812 9170972403 8983509001 9675208021 0462527962 5498701257 1810788813 4618264091 3108413839 4117347555 8926305650 9918720553 8147855080 0273969574 7063329213 0934665741 6906742647 4345792531 6216394500 3241822533 6727800838 3215073951 5726899350 2186982572 3420323171 2372144750 5850795950 7311180160 4225454589 2741037091 6327646210 2084877350 3611263311 8528514306 8594034858 0267404027 7977371728 2420731690 6285534602 8783147067 8456323305 3386148635 9291369317 3755216976 3603244709 4676882062 1839296978 2856790261 1640678369 1142394241 8407718759 7642042663 4807184866 3916548900 0760327352 7915247612 3365913697 0515926602 2700436145 4010639747 0598330945 0638755493 9499876916 1406067816 6916507440 4081924759 8016284323 7612498524 5520173377 6130039059 6064545635 2291915947 9444645110 9761028633 5980677473 9278752330 6845209790 0055049734 9678614898 9034988798 2507769035 2158418367 4113589185 3416855781 5763480483 6643251255 9050372269 6639631733 7248146863 6852440569 7027570278 9333216227 7577779647 1338787285 1023933617 8966729167 5099861314 4046927110 3837019760 1057555269 9969295492 1018877074 8581666650 9878159413 2390695719 7412309304 1818740260 2910557289 0975549513 0721907750 4169191738 4913411040 3248500700 4479738151 3084167748 8070965396 0655000535 0049740667 7586409372 3915451741 8711913281 6878343369 3914315148 5103786620 1512613771 0419642706 0514232749 9615076078 8551511404 2089856666 4140050262 5900958415 0574902810 1578009113 4848523890 0262138935 5967318770 6143369198 1756749467 3758414850 6460872043 0770606632 7475263536 1955659768 0312535737 6861947211 6460101725 7723169897 1882451997 4520681435 3982602051 7623286084 6407646919 0721291672 8774989268 9142078437 1095775602 0223372891 4083099533 5324592649 1106645932 2637812101 6980197531 1748217034 1780526174 8557766791 6595323625 9781325924 0599568743 5464944551 7470658134 6389381961 4999910973 0765587792 8084304630 2594228165 3611519608 6563326866 0872195350 7061643716 3672000871 7574282607 3673082981 3617454924 1106774475 7072999723 7203639798 6908755783 6641392195 4421283216 9356945614 6487880285 1500441951 9348722112 1483341141 7767903834 7673658091
• c₂= 17239 1220006205 9837228411 6234449164 6654271104 8106638330 3349544743 7993795997 6638828497 3491031725 0045127643 0389956072 3270121069 0144617807 0791866599 0318727734 9787713583 6479202360 3934186510 7053006175 5137638935 6866652081 2078380180 5984599071 7389932872 9723687606 6233435195 3787310583 5333994741 7903216197 5581156669 5644383065 1156380806 2586932554 6607494169 1756186694 2277666943 1260184538 4161433013 4631305627 6569197248 4121549999 1615253769 1472204533 2650692712 7473327632 4613297738 1232773691 6405784038 5028428315 7601780426 8231500698 6237748923 8115751369 5886560013 6419654338 7353640034 8375011837 6830394313 7719914871 0344769774 1143369765 4294143959 9935673607 0985717459 6065489130 2172383161 8626487339 4101827725 2197811726 1974148707 5479896735 2592813102 9542207887 6316321175 0243326559 4977204228 7370574446 6285397030 1120745423 5836182974 4881290550 5084722551 2991752225 1503825692 8107506702 1653034644 9448919330 9181981536 1967523755 5163450530 6709506436 4522239418 9591577126 5512226702 7604900803 7402978446 1669148426 4388856843 0411748754 8397963090 8841970213 3474196072 3368191738 4145965412 6408479032 9946808370 4733918438 9587197167 2276671468 6923562426 8087593336 8170950967 1263500394 5682299531 4751674148 4863910482 0540839095 3180607762 7300800234 3032481459 2893647293 2883380621 9138023468 5105770842 5565283193 8182945996 7786448606 5900893064 5746136386 9097161225 4014362516 4713713712 0674653615 1655570066 7018536995 3994813684 6476375443 2274664219 0772604676 8480867282 5185330629 1833907201 7956088357 5987176683 9475856029 5644526906 3962326918 0725618186 6127034931 9642096080 5157287533 6156747696 4623052266 3169057590 0180038406 2024899159 3968448731 8135476811 4247837846 1804124183 0077642005 3624587423 9039767275 9502372003 6625442209 5027333531 4035052685 4993641906 4465072272 6818669402 8640160144 8168432454 8661665663 2794541521 3393450620 5132348285 5227174307 9649118300 3343977221 7632802752 4942832160 3510433032 1392144244 3307279574 1638363331 5629120779 0969803942 4363487117 7700748810 9507609748 3696625045 7740999975 5594290807 3386219613 6221349697 8742818474 0503375312 5308808412 6692623190 7553863818 6624024341 6977276816 4122100660 7074050657 8114594096 1390868971 5543513974 1845123396 2713552848 4622965845 0617117866 9921218908 2001805977 1319657807 5284349452 5185577619 8317822825 2447647250 2982191373 1239645821 1495585258 4365336970 3724860772 2704823903 7114805151 5485465973 5351028349 1089995844 8369877579 0341511296 2731938819 4748819003 7317129887 8544987482 8149579251 5654131868 8079356514
• c₃= 13463202 4723226248 0428505281 0699920139 8241687498 6670036739 1734416124 2704153411 2489567651 5941084805 0750020287 4301920931 1294197883 1962501095 9338089989 3085808398 1427737132 8581515677 1489089682 2254879216 8377411526 3580721213 2010218062 5661920753 9016584437 5342286562 6454272086 2422217505 0605016494 3933050091 9163605962 4266735872 8136119453 1459551630 7416571391 4305592471 9713352464 8350090258 2182976079 7410146120 4325372494 6034917395 1178585321 2221682680 2171604646 3143108113 8501152937 3727982146 1255501355 9556994974 6833558094 3620062073 4534375229 8056827530 4223797500 5659023179 0966765069 3355811841
• c₄= 140 8788113197 4919936048 3075719668 8985923740 4310938636 2123102667 4022657230 3262494660 5595766947 3986993205 9802894322 9736331559 7409404663 3935399876 8379624048 3245734951 3734888837 6745736505 3246697376 8299681101 4672702172 5185766709 6733777501 6206538220 9056469000 5879018568 3203234388 3462486911 6104043680 5845923193 5234228559 1289551928 6392280220 5506446600 0752162484 7213875197 3873776268 5616367544 7589080458 3121842090 3454985814 5157710970 3054659990 9551551561 3271622258 6842820530 9252799271 7682889796 3848631671 5307665597 1721702471 3731246039 3314214358 7197978239 5582673789 0849062851 1436385023 6964152347 9347930307 5272131608 9886250683 5676411304 0509107791 8875639323 9518808849 7589851724 2273610482 5737971287 4090420896 4169956618 4265872020 3005157425 7543646855 6104874316 4607147913 9911484401 8834961951 4779727623 8421189564 3272978666 3231925652 0329589350 4536768949 3005240269 1952706793 4359492624 0312406992 4007281611 1573513586 0874360592 8724947683 8529388319 4216892659 7808803415 7474238243 8016949187 0957277459 3165853455 8634869338 5292282506 9652860553 3714452718 8502481876 7668584269 5325447998 0236145958 9405153891 8385326084 7984463827 0699577903 1550429100 3100600705 8781781382 0619808160 7458422097 8723166553 9654647011 8937783175 8399540446 5349525349 3258170913 6819071966 8295365866 1544200501 5963616798 6632616792 4321041855 4526980288 2944126826 2388063203 6816722298 5527780784 3104964628 8452798568 9430185597 2190836578 2199563509 9111487979 2461019386 0809656400 6186930523 3158450280 7622247310 4862032618 1293458212 7450866269 6761793669 8718858603 6252356795 8726648988 8885241796 0565690994 3624423440 7074004073 3152391862 6874085470 5790173479 5689893741 8133567276 9131188458 9996962014 5362068671 6103736802 5521863974 4532062616 5803364838 5608371638 8829753903 1415352756 5092429346 1539572714 5943739954 2150081255 2468043544 8148860211 9815468966 7150357359 3147839302 4153261464 5704333241 7298939255 2254460798 2406182113 5630828298 5292365282 3372279443 1455289706 0255181587 5982258186 3421881360 4518210581 7621438549 1624519884 5254386257 2051355508 8765704432 8192954597 4878621078 7800703597 9943284350 1380122240 1986585938 9963110839 0114383239 3612599416 5366830183 7740137509 0450923771 5067854762 1168926283 9919088992 1041962505 3210186687 9621781764 5014262627 1560953420 2621013743 0234812490 2494118677 1974353690 6294155715 4395553084 4749263775 5891238787 2183676735 6998310939 1657185303 8643115414 4677161033 7329422720 2802157288 4235902622 7775567511 4387424595 0867643647 1934425772 6810741590 9388897062 6337786256 4864106047 2718143763 0851083512 4145312292 9188529660 1132262028 8695381307 2596256547 3201406838 2659351496 2544197169 5476832086 4859717100 3814373425 9332596959 5648759380 2671021664 4478437446 4967561470 7846014180 6967323896 5809681348 7396065152 7098178630 8986997627 0035739680 6106616741 4711355390 7643985787 7936791888 9472392582 5158812516 2924775682 6701902166 9231671836 2882529305 2165386412 7662458435 8036331288 0509955549 3570847026 1621846319 6849342672 8484366419 8391636643 7843283095 0226462015 8917479418 2230966230 8708616657 0608168172 3997909913 7269436457 7647338379 1472309967 0156937954

Square Checks

For t = 0 to 5, we prove that Q(t) = (c₁+t·F)²+4·t-4·c₄ is not a perfect square. This is done by checking whether Q(t) is a quadratic residue modulo a variety of bases. If it happens to be a QR in all of the bases, we calculate s = floor(sqrt(Q(t))) and show that s² < Q(t).

• Q(0) is not a perfect square: it is ≡ 61 (mod 63)
• Q(1) is not a perfect square: it is ≡ 5 (mod 64)
• Q(2) is not a perfect square: it is ≡ 6 (mod 63)
• Q(3) is not a perfect square: it is ≡ 61 (mod 64)
• Q(4) is not a perfect square: it is ≡ 14 (mod 63)
• Q(5) is not a perfect square: it is ≡ 5 (mod 64)

Continued Fraction

We approximate c₁/F by a continued fraction u/v such that v is maximal while remaining less than F² / N^1/2 = 881605847 5300195337 7388355575 3434676084 4223665474 3176541147 6505717389 4084996283 8060117849 6122517768 7078251112 9792761162 5354277827 3431320268 4792575654 6947077242 6476233531 0562702405 3044664230 0769496904 0518447946 6229928988 0073992750 6777346497 6489520505 8706412368 1630496560 6795903459 3607696701 9250457542 2945631982 4344420537 7047466090 8907907727 2547977196 0772923060 9486372206 7038949433 0168542341 8044836327 4038561543 0089024085 1241906147 8258524064 2567614765 5556533497 4769728087 6271936917 1499990182 0167677720 4943438698 6143556731 0685883534 6437219983 2081397038 4690302157 9663096976 1487737126 2015635968 9030732344 9238009930 9414013846 2591650511 7860567712 5235787490 1035383036 9917458114 5368361141 3709038420 3220831357 9846267726 4249293822 6660233747 4517190477 0346619915 5972825606 6415465235 0232452384 3667127298 9066062849 0172919444 8133467726 1614247998 6209166686 7575712833 9334855522 8752518482 5873920268 0925995213 3750606097.

With those constraints, the unique continued fraction is: {0, 1, 10, 67, 1, 13, 12, 1, 47, 1, 3, 2, 1, 1, 2, 3, 3, 3, 2, 1, 3, 5, 3, 3, 1, 1, 2, 5, 4, 1, 1, 1, 2, 6, 3, 2, 2, 1, 2, 1, 2, 3, 1, 9, 3, 6, 1, 2, 2, 10, 1, 9, 1, 2, 2, 2, 14, 26, 9, 1, 9, 1, 1, 10, 2, 1, 18, 2, 1, 5, 5, 3, 2, 24, 1, 2, 2, 1, 8, 7, 2, 2, 7, 1, 2, 8, 2, 4, 2, 14, 1, 2, 1, 8, 2, 5, 1, 5, 1, 5, 4, 4, 2, 4, 8, 1, 2, 2, 4, 1, 1, 1, 1, 23, 1, 1, 7, 7, 1, 1, 6, 3, 37, 9, 1, 1, 2, 1, 4, 1, 19, 2, 1, 3, 2, 1, 2, 12, 1, 2, 3, 5, 1, 2, 9, 11, 1, 6, 5, 1, 16, 1, 1, 1, 2, 1, 1, 139, 1, 3, 1, 2, 4, 1, 3, 10, 2, 4, 25, 1, 4, 3, 4, 2, 1, 25, 7, 1, 2, 2, 1, 2, 1, 2, 1, 1, 6, 1, 1, 2, 1, 12, 1, 3, 1, 1, 1, 1, 1, 2, 1, 3, 3, 30, 1, 9, 1, 5, 1, 3, 1, 1, 4, 1, 4, 12, 4, 1, 1, 2, 1, 2, 1, 8, 8, 1, 2, 2, 1, 12, 1, 337, 1, 5, 1, 374, 2, 13, 2, 2, 1, 9, 3, 1, 40, 2, 1, 9, 6, 3, 3, 1, 1, 1, 4, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 45, 1, 1, 41, 1, 3, 3, 1, 2, 3, 1, 11, 4, 6, 1, 56, 1, 12, 3, 2, 1, 2, 5, 25, 2, 18, 1, 1, 1, 3, 1, 2, 33, 2, 3, 1, 1, 1, 1, 2, 6, 15, 2, 3, 1, 69, 1, 1, 1, 9, 1, 1, 2, 2, 1, 1, 4, 1, 1, 1, 1, 4, 1, 1, 4, 2, 1, 2, 39, 1, 1, 28, 1, 1, 1, 21, 2, 4, 3, 1, 1, 1, 5, 3, 4, 1, 2, 1, 5, 7, 1, 3, 1, 9, 1, 3, 1, 3, 5, 4, 1, 7, 1, 3, 1, 28, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 5, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 3, 2, 211, 44, 1, 3, 2, 1, 24, 5, 2, 20, 3, 22, 10, 37, 3, 1, 2, 1, 7, 3, 125, 6, 1, 1, 3, 7, 2, 2, 1, 2, 1, 1, 1, 1, 2, 10, 6, 3, 1, 4, 7, 1, 9, 2, 1, 14, 3, 3, 51, 3, 2, 11, 1, 2, 5, 3, 1, 1, 3, 8, 4, 6, 1, 1, 1, 13, 1, 3, 2, 13, 1, 1, 1, 1, 45, 1, 3, 2, 4, 12, 3, 5, 1, 1, 3, 1, 3, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 3, 1, 6, 6, 10, 2, 1, 2, 3, 2, 1, 1, 1, 1, 4, 4, 1, 48, 2, 7, 2, 2, 1, 1, 3, 1, 24, 1, 2, 5, 2, 21, 1, 1, 2, 1, 1, 6, 10, 4, 1, 11, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 47, 2, 1, 2, 7, 2, 1, 17, 1, 30, 1, 4, 1, 1, 2, 5, 2, 1, 3, 4, 1, 1, 2, 2, 6, 1, 5, 3, 1, 7, 11, 1, 2, 1, 2, 2, 1, 13, 2, 1, 10, 5, 74, 5, 1, 3, 11, 13, 1, 1, 1, 1, 2, 1, 14, 5, 1, 1, 2, 2, 1, 170, 6, 3, 5, 1, 1, 1, 1, 1, 2, 1, 6, 1, 61, 3, 1, 1, 2, 3, 1, 35, 1, 1, 1, 52, 1, 3, 1, 1, 1, 11, 1, 152, 24, 1, 6, 5, 2, 6, 4, 1, 2, 1, 3, 1, 47, 1, 2, 2, 8, 3, 2, 1, 1, 2, 1, 1, 1, 1, 54, 1, 1, 4, 1, 2, 2, 1, 6, 229, 1, 33, 1, 4, 1, 1, 6, 1, 1, 2, 2, 1, 18, 8, 4, 5, 1, 1, 3, 6, 1, 2, 4, 3, 1, 1, 1, 1, 5, 1, 1, 2, 1, 1, 17, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 7, 1, 1, 3, 1, 4, 2, 1, 2, 1, 25, 1, 29, 3, 1, 1, 1, 16, 1, 1, 2, 29, 31, 1, 2, 4, 1, 5, 1, 3, 7, 3, 2, 2, 4, 3, 1, 4, 1, 1, 1, 1, 19, 1, 1, 10, 1, 5, 2, 5, 1, 4, 1, 3, 316, 1, 2, 1, 41, 1, 4, 1, 3, 1, 1, 8, 1, 1, 1, 766, 33, 2, 2, 25, 1, 67, 4, 1, 39, 3, 1, 1, 2, 1, 93, 5, 1, 1, 11, 1, 9, 1, 1, 1, 1, 287, 1, 1, 6, 1, 1, 3, 2, 1, 1, 1, 12, 2, 3, 2, 1, 1, 1, 4, 2, 6, 1, 2, 4, 10, 2, 4, 5, 3, 1, 3, 1, 1, 2, 1, 43, 1, 1, 11, 2, 3, 37, 2, 1, 2, 3, 3, 2, 4, 1, 1, 2, 1, 4, 1, 3, 2, 2, 44, 1, 9, 1, 5, 1, 1, 2, 1, 1, 1, 2, 1, 5, 5, 3, 4, 2, 1, 1, 1, 2, 93, 7, 4, 2, 10, 1, 1, 163, 1526, 3, 2, 2, 1, 13, 2, 1, 7, 1, 2, 1, 3, 1, 1, 2, 1, 1, 6, 1, 1, 108, 1, 1, 1, 1, 1, 3, 3, 209, 4, 2, 1, 8, 1, 1, 1, 1, 1, 6, 1, 3, 1, 1, 1, 17, 9, 4, 1, 1, 10, 1, 2, 1, 2, 1, 8, 1, 1, 1, 3, 172, 1, 7, 1, 2, 2, 1, 6, 2, 9, 2, 2, 3, 1, 6, 2, 1, 56, 1, 11, 1, 2, 20, 3, 4, 1, 1, 3, 1, 19, 2, 1, 38, 1, 2, 1, 6, 45, 1, 1, 5, 2, 1, 1, 21, 3, 1, 2, 4, 1, 2, 10, 4, 1, 11, 2, 2, 1, 14, 1, 4, 1, 2, 2, 1, 2, 3, 6, 5, 65, 3, 1, 6, 2, 4, 2, 2, 1, 1, 7, 8, 1, 1, 4, 1, 1, 1, 5, 1, 1, 1, 13, 17, 1, 3, 2, 3, 18, 9, 5, 1, 1, 1, 22, 1, 1, 1, 1, 3, 2, 3, 1, 2, 32, 7, 7, 1, 3, 1, 1, 2, 4, 2, 1, 2, 2, 1, 1, 2, 1, 19, 1, 1, 22, 1, 7, 2, 1, 4, 1, 11, 8, 7, 2, 1, 172, 2, 13, 2, 52, 1, 1, 1, 1, 4, 5, 1, 7, 1, 2, 1, 8, 19, 1, 6, 3, 1, 3, 3, 3, 17, 1, 11, 1, 1, 1, 1, 1, 9, 9, 45, 2, 1, 5, 1, 1, 2, 1, 1, 11, 1, 2, 1, 4, 1, 2, 1, 20, 54, 6, 2, 1, 4, 2, 3, 500, 6, 1, 1, 3, 3, 13, 1, 4, 3, 1, 1, 7, 4, 1, 1, 27, 3, 1, 1, 4, 1, 1, 1, 7, 1, 14, 1, 2, 1, 4, 1, 3, 8, 5, 1, 1, 1, 2, 5, 38, 1, 1, 4, 1, 1, 1, 1, 11, 1, 1, 5, 6, 1, 5, 1, 16, 7, 1, 2, 1, 4, 18, 4, 1, 1, 7, 1, 2, 1, 48, 5, 1, 1, 1, 1, 3, 1, 1, 4, 3, 6, 3, 4, 1, 1, 1, 2, 15, 91, 1, 11, 1, 2, 1, 1, 1, 7, 41, 1, 6, 1, 1, 51, 2, 3, 1, 55, 1, 1, 2, 2, 2, 1, 20, 3, 2, 1, 2, 10, 1, 16, 2, 1, 1, 2, 1, 1, 1, 133, 1, 2, 2, 1, 3, 2, 2, 4, 1, 8, 1, 13, 1, 1, 3, 2, 4, 2, 1, 2, 1, 26, 2, 4, 11, 1, 7, 2, 1, 2, 2, 6, 1, 20, 4, 25, 7, 2, 8, 1, 1, 3, 2, 1, 3, 3, 2, 1, 2, 3, 1, 1, 2, 1, 1, 3, 3, 15, 1, 2, 1, 3, 5, 8, 20, 1, 8, 3, 2, 1, 1, 24, 10, 1, 1, 1, 2, 26, 1, 1, 15, 1, 1, 4, 2, 26, 6, 3, 1, 5, 1, 13, 5, 3, 1, 7, 2, 1, 1, 11, 9, 1, 1, 1, 6, 4, 6, 1, 16, 4, 1, 12, 1, 3, 1, 3, 9, 3, 2, 8, 3, 7, 18, 1, 2, 24, 1, 1, 1, 4, 2, 2, 14, 2, 3, 19, 16, 1, 1, 3, 2, 1, 1, 1, 1, 1, 6, 10, 1, 5, 1, 24, 3, 1, 2, 1, 12, 1, 1, 1, 2, 4, 49, 2, 2, 1, 1, 7, 2, 1, 8, 1, 1, 1, 1, 2, 4, 2, 4, 2, 2, 1, 1, 6, 1, 11, 1, 34, 11, 2, 8, 1, 1, 1, 18, 1, 6, 2, 4, 2, 1, 30, 2, 33, 2, 21, 2, 1, 2, 1, 1, 19, 1, 2, 2, 2, 2, 4, 1, 5, 1, 1, 8, 1, 31, 3, 1, 29, 1, 1, 2, 1, 1, 2, 4, 1, 9, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 19, 39, 1, 1, 13, 11, 1, 1, 43, 2, 1, 1, 4, 2, 3, 2, 1, 1, 1, 3, 203, 1, 2, 1, 3, 1, 1, 7, 1, 4, 2, 1, 1, 2, 1, 2, 45, 6, 1, 1, 33, 1, 1, 1, 5, 3, 2, 4, 7, 1, 1, 9, 1, 1, 12, 2, 3, 1, 3, 1, 94, 1, 1, 1, 7, 1, 25, 1, 4, 2, 5, 2, 3, 4, 1, 1, 3, 2, 1, 1, 2, 7, 1, 1, 12, 3, 414, 1, 34, 1, 3, 1, 4, 9, 1, 5, 1, 2, 1, 10, 1, 3, 2, 1, 61, 15, 1, 9, 1, 6, 1, 3, 1, 1, 6, 1, 11, 1, 18, 1, 1, 110, 3, 2, 2, 1, 2, 2, 7, 1, 6, 1, 4, 3, 2, 2, 7, 11, 3, 19, 1, 3, 9, 1, 1, 1, 16, 2, 2, 35, 2, 3, 2, 2, 5, 1, 1, 1, 1, 45, 3, 1, 1, 33, 3, 2, 4, 6, 1, 3, 1, 28, 5, 1, 1, 13, 2, 6, 1, 1, 6, 2, 4, 24, 3, 3, 14, 6, 3, 1, 1, 9, 1, 2, 2, 2, 1, 4, 16, 1, 1, 1, 1, 1, 1, 2, 1, 1, 29, 12, 2, 3, 3, 1, 21, 1, 5, 1, 3, 1, 5, 1, 3, 6, 1, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 7, 5}, giving these values for u and v:

• u= 613496672 0524501119 5292544736 0955608421 9868029222 5336095204 4635132716 3090739738 4574666575 8357564284 6100851736 9832603563 3597290822 0566304975 6759464297 3948929357 7192611774 1849557249 8146608968 3720758161 3460637002 8759556671 9858716979 6479805758 7162663513 3979750380 7814264405 1131419144 3015404044 5153435780 7833243921 1315945892 8856079403 9496171724 6506525375 2784596217 8981982057 1035621999 5929466293 6330957626 6017229398 3088733209 6441738118 1335045579 4062581470 4317665964 6340965371 4996729112 9728514493 7571452137 3648376736 5153056750 7481633621 8441129158 6240501562 0218582565 7031690182 5849291427 3210771673 9532735315 2556380091 1994401239 4344348902 9213868695 6931916660 5163493300 3952543687 7501862481 5944294184 6955722657 6129248351 9644878653 8944847071 5299044171 2859363629 0787403746 4435032972 9435910743 4927442176 0634041016 6236761009 9422910515 4653293992 6699815232 8000507143 3191137557 1426143593 1694739377 7828980436 2610535541
• v= 674756157 5687860251 2158432789 2505258319 8813881760 8664890937 7485696587 6499142050 1934716727 0869248021 6292562889 1430606081 3392709136 5422575400 3498011732 4176224923 2657663987 3468424727 8891287598 9436192264 0143625294 1871766539 4997717288 4011862862 7540973445 8312956920 2572440807 4277680844 0636260242 3162039609 6790779877 9649686188 9923250284 5557186494 1980991405 6596656998 5030741886 5036046475 4168152743 8741089503 8081402883 1974178819 8532997732 0028060604 3780986606 8532494096 0915851606 8170045226 6978330438 0392600021 6496015459 9652816329 1219544734 0135131623 1275138521 3466139334 4201740611 1019220238 8586472315 1058757901 6274365636 3153455809 7374056334 9354219522 1337580665 7955329830 3257062729 9803549502 5233133087 1756698168 3421711772 0163361732 3491626474 4881855117 2606496351 7555600105 9999606815 6481781384 0287350714 3997059107 4559081290 8131006883 6743782596 9772523169 2998720136 4441714870 9475957662 4124169616 9616731227 6451622376

We also need to calculate d = floor(c₄·v/F + 0.5) = 908437 8768794994 5967317320 7096368621 2943418674 0039039109 8692748157 6609600291 6118592254 8542450159 1451000025 3372742680 7621649665 8941498697 6990825573 0953955879 8048618991 1350569750 2948533965 8490283098 6400203702 7790187496 5456335747 4718989254 6809583588 0557002448 4250021130 2437283659 8877815173 4725157999 5706396323 9009094120 4792976042 9701512220 1333979443 4788947207 3081959838 8624617025 5687940017 1367707020 6886320104 7064855482 9705858986 3511753361 7618098046 7717479681 8851843477 5030684416 8042706173 9870434302 4730492949 0224235877 3118341851 9406432683 4928480784 7801494213 1452701595 9768347937 6235005868 7272448036 4538521784 0641736621 6487904781 6952713800 9825230524 5577633211 7312122300 4804649209 8846657479 1128062260 0211516816 7408031486 5334064731 0140096105 8037976634 8526514059 1461245894 7043278294 3235231639 9791110081 2964412407 1145169862 7058396079 5295181169 4299238526 9012526890 2536359038 7129612247 6706041087 4642539788 5394688267 2530663383 6122219078 8164190329 7412867436 4981036655 4945105262 5522523548 3182047533 8690072572 1015170901 8576144545 2878938858 3300390870 8633525629 0564149509 5043927052 6889646281 2566173420 2268413578 2585869198 3452873555 5280181651 6725338757 1557549052 1727522652 8204145120 7930893447 1643527556 2268083085 6627520656 5519564542 1771013964 0456227040 4938021515 5706914777 1222005780 7515686097 7603903380 3225382288 8118170165 7972593583 3268136584 8820406346 9560445939 8242159436 6413166880 2631009119 9831981957 8282619234 8972958929 9729001272 3367766805 5980363646 3709309860 5093611331 9650298386 1014741337

Cubic Polynomial

We now consider the cubic P(x)= v·x³ + (u·F-c₁·v)·x² + (c₄·v-d·F+u)·x - d, which we express as: z₁·x³ + z₂·x² + z₃·x + z₄, where:

• z₁= +674756157 5687860251 2158432789 2505258319 8813881760 8664890937 7485696587 6499142050 1934716727 0869248021 6292562889 1430606081 3392709136 5422575400 3498011732 4176224923 2657663987 3468424727 8891287598 9436192264 0143625294 1871766539 4997717288 4011862862 7540973445 8312956920 2572440807 4277680844 0636260242 3162039609 6790779877 9649686188 9923250284 5557186494 1980991405 6596656998 5030741886 5036046475 4168152743 8741089503 8081402883 1974178819 8532997732 0028060604 3780986606 8532494096 0915851606 8170045226 6978330438 0392600021 6496015459 9652816329 1219544734 0135131623 1275138521 3466139334 4201740611 1019220238 8586472315 1058757901 6274365636 3153455809 7374056334 9354219522 1337580665 7955329830 3257062729 9803549502 5233133087 1756698168 3421711772 0163361732 3491626474 4881855117 2606496351 7555600105 9999606815 6481781384 0287350714 3997059107 4559081290 8131006883 6743782596 9772523169 2998720136 4441714870 9475957662 4124169616 9616731227 6451622376
• z₂= -325138 7901665543 6677232531 5679187859 3034231439 2675308930 1282069012 2675880626 8718232053 4962692182 4248766767 2474109969 2010133207 9619651126 1355938789 9853730164 7756049193 7779956253 6072632182 2053643826 4315753811 4159351457 1423205551 9051589551 4906872904 6221317470 8587765934 2103632155 3150898217 0988637759 3673125647 0744106349 5733710009 7063785826 5480191947 4798241121 8902811642 6854440534 0129023467 0256306435 2776501881 9784912265 0843553646 4080400464 7701692588 0183383401 4517292198 7414183776 0403125317 2565029959 8703611178 2893961986 8973240108 7243038098 8474788513 0527704729 5486974151 4495594907 1397705160 3507523990 8012294608 6101060263 3476513133 1148332467 5324078037 1362253575 4721276217 5063359094 5320298124 9308281910 3448826512 7620102132 3544943095 2175117903 6298303262 8452051155 1228051783 9749899293 0259318548 7370800285 1158002682 3151475210 3087716363 1577984152 2996294751 2408661416 4297975004 7995585705 6656062228 9852320105 4466448886 9585819886 9789776953 2913829219 3777307002 7481295239 8194772961 9156051804 9401405778 9011124548 3409700489 9108114070 3321105179 9750299959 0430910855 5008005264 1289191244 4929240645 5501725985 9480618631 7619150748 2175646761 6860776307 4224951256 5621989321 3832104263 3606520603 3125505507 2639792390 9136848069 8342392334 0550107111 4214547531 4046345405 1722058873 0028764458 4101175650 5052620776 2684213804 0291547868 7118817985 7802542318 1024170180 1673585627 3391823755 9045129085 6930142491 8801569158 7742680966 4020876776 4120282127 5476187416 0608996885 9084788324 8907913690 8372505393 3049905999 5454054776
• z₃= -19591 4452465901 1890901455 5242226699 8710171267 6930247932 7825207622 4674440400 5723673131 7588187344 2956402114 8590603261 2621603798 8320153516 0212402083 3793526626 6194919194 8771863358 9794246096 9568965558 4592530011 2573513322 6941564014 6328576601 0470528346 8217036109 5882258636 1455837680 9019333037 0533771696 9135434714 5189763386 3392222992 7955486511 4145621499 1172935308 5153636550 7295463138 9120381557 7891642549 5546290694 9596533527 5786307084 9758312090 9903008100 7954895725 7674915219 4648015142 8048842313 8127943772 4863916640 9335484797 6653939251 4396764722 7727781755 3074916687 8659533268 7658676019 1386114995 1573447857 7576032649 7428293158 1587495410 9814181282 2877907542 4403335697 3356663429 6805611734 7960665834 9377294239 5727671195 7126844679 5198658236 4061499153 3436865621 9837963546 1823493020 6591585875 2592236443 1877840816 1760071211 0586707024 1249984755 8832709899 7295718534 3497512835 1828436375 8492554688 8685643725 5774569173 3370930897 4477085411 7592268711 8372077897 1452190219 2985163450 7138991743 0769677349 7191158932 6017138535 9483725951 1296878316 2407151943 9295294504 5405994594 8312256258 4521340582 1509739815 7874615478 5784965585 0994943345 5013556007 7511908383 8899842719 9352092746 8728304826 1682869813 6634857383 1660481746 3311922018 3374496752 2821914175 8845458682 2819180846 8876436369 2230278757 1031273148 1582151659 1440694550 6281547361 6973195075 5526241027 3033927417 7356996544 7320427299 8775307020 6211844008 4296046773 4210586704 4135061787 5060195370 9980480726 2052022088 1419397556 8418619142 1228948600 7958797896 2659595438 1914638904 0201364163 7283290927 7276745586 9034624150 0885393304 8376467087 1000561237 3338703640 0772441774 2726181890 0263731189 7898430678 5699520817 8656089083 4005830185 1263927227 5525044408 8927103286 4878503853 7847103769 4792448306 2853215526 8134830600 7334647554 1450930590 8401371494 4709493393 5510737433 9078399492 7260755654 1472344807 9363613812 0402699852 1098262670 9505417984 9622778783 7333715755 0997409472 6250719529 7493858398 0401583892 0535666068 5550674043 8835902112 7840341461 3603502613 6256314117 5862771903 1098145947 2606240283 7791676918 8783292734 5794805953 4975123703 5337938958 8108594871 3439866636 3032027287 5607384254 7531310846 3663710001 3320721507 1375559474 8345532804 3038020870 5525934138 0467754405 0999539594 9187936561 6861550866 7391678237 5332638384 2360861978 9400218408 1642937215 9849722118 6708185620 1480448318 4745001460 2390536186 4773126375 8913985717 8042552216 0614182311 8795637660 2660068142 3335255948 7674725529 6057323835
• z₄= -908437 8768794994 5967317320 7096368621 2943418674 0039039109 8692748157 6609600291 6118592254 8542450159 1451000025 3372742680 7621649665 8941498697 6990825573 0953955879 8048618991 1350569750 2948533965 8490283098 6400203702 7790187496 5456335747 4718989254 6809583588 0557002448 4250021130 2437283659 8877815173 4725157999 5706396323 9009094120 4792976042 9701512220 1333979443 4788947207 3081959838 8624617025 5687940017 1367707020 6886320104 7064855482 9705858986 3511753361 7618098046 7717479681 8851843477 5030684416 8042706173 9870434302 4730492949 0224235877 3118341851 9406432683 4928480784 7801494213 1452701595 9768347937 6235005868 7272448036 4538521784 0641736621 6487904781 6952713800 9825230524 5577633211 7312122300 4804649209 8846657479 1128062260 0211516816 7408031486 5334064731 0140096105 8037976634 8526514059 1461245894 7043278294 3235231639 9791110081 2964412407 1145169862 7058396079 5295181169 4299238526 9012526890 2536359038 7129612247 6706041087 4642539788 5394688267 2530663383 6122219078 8164190329 7412867436 4981036655 4945105262 5522523548 3182047533 8690072572 1015170901 8576144545 2878938858 3300390870 8633525629 0564149509 5043927052 6889646281 2566173420 2268413578 2585869198 3452873555 5280181651 6725338757 1557549052 1727522652 8204145120 7930893447 1643527556 2268083085 6627520656 5519564542 1771013964 0456227040 4938021515 5706914777 1222005780 7515686097 7603903380 3225382288 8118170165 7972593583 3268136584 8820406346 9560445939 8242159436 6413166880 2631009119 9831981957 8282619234 8972958929 9729001272 3367766805 5980363646 3709309860 5093611331 9650298386 1014741337

We need to prove that this cubic has no integer roots r such that r·F+1 is a non-trivial factor of N. Clearly r (if it exists) must lie between 1 and R.

The real roots of P are:

• -1+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• -53883997 7283423418 6845316048 0586838263 5880569806 3111372389 7374575073 3264145567 3039570841 5212502557 5626150462 9798453373 3780779894 9720266162 4003148285 3298310476 9803371200 1671681782 6463610756 4283387653 0858623489 1882156653 8200482555 6943301748 8520547020 6011446818 8954828345 6626195687 8585242202 7628994872 0526501759 9745529859 1283476632 9363532809 4589964390 4600517738 8188627263 2500114921 2030677830 9295266999 6041572762 7205172920 0749107637 0661338695 8288602100 8458859981 9296828869 5857003206 4208519885 7371586621 8684226399 8066122981 0811442366 6598178998 4736951817 4637859612 9339476746 6810660046 0354917884 1441716877 3307868345 5646543486 4641000774 2480213277 6479109305 8088021283 7181434281 5323597949 2360357024 8591739394 7221242040 1130242013 8842990019 1720801243+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• +53883997 7283423418 6845316048 0586838263 5880569806 3111372389 7374575073 3264145567 3039570841 5212502557 5626150462 9798453373 3780779894 9720266162 4003148285 3298310476 9808189811 8466534307 1850055552 5165992775 8340328167 5474377935 3419049918 1663925487 5411711405 8930390939 3773049971 6569290440 9637212328 5165672306 7221521629 7814143935 4112659354 1275037570 3725740179 5143931456 9002746992 9324904445 3454724110 1052938482 6124941797 9443388629 7699283002 6459556175 9339586934 0688603723 5374111984 6437009071 9792594302 4186106218 3845503276 8194344722 6108332242 5205819973 6377787288 7318361656 3541881846 5020266892 0193650845 9107567938 2912487347 8714299702 7650109918 5503512391 5686142318 3760251715 0128593811 4462131028 1968857669 3813200485 8956332282 3539744791 4860079811 7636995044+ε∈(0,1)
  (Root is not an integer)

There are no integer roots of P in the interval (1,R), so the proof of primality is complete.