Primality Certificate for (5968^2341-1)/5967

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.226524% 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.226524%

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 = 391 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₁= 6935380784 5387993392 0960299103 4445343424 2520088835 4272686403 2121413078 3041482729 1261021126 1148595985 3864480973 8886918973 3606744054 4074408549 5485392801 3267004305 4074481963 3607128087 6792129879 8769667519 7616452666 5357604802 6287885790 4932857240 2675027158 5046446089 6973728293 0773414212 9612969752 3834928816 0653303858 2600079662 6474653690 7025789482 3669170271 6976016180 4864707230 3274449966 8510584264 0062977629 1276906598 0182431982 2640393027 4740558917 0828923218 8559973207 7862610812 6285635012 9342815277 3086379780 8706589017 9061680983 0777470165 3059780631 1220977751 6018857847 3016640310 8788843960 0933907277 6535630940 2871499676 3013250344 9632472116 4434003713 0201343774 0924575998 3973389581 8565087664 7689509394 8756122407 5895558349 2080898218 2803000211 9924246078 4877008407 1895371363 3992531534 7116379013 1290412278 9024322623 0258524102 5335085905 5458632629 2148734926 7909019116 8444300113 6956871113 2774737955 9879123763 7602185377 6775282304 0749621683 1412457152 6736045520 3927535509 9849447882 5803277026 8582106416 9659598918 6781600907 3052443852 9642339612 3855782080 8016873107 0451793735 5024601625 2405899880 6867919809 4640128916 4254382600 2850908690 5231091867 1219826753 1283837227 9387687815 4165860841 2495627215 2388219475 3798405640 1151442065 7195027686 2782452157 3079676763 6289519633 2316888271 9741177987 7265400268 3700846027 1326525768 7144781828 7968179467 0755434764 1433198202 6919296212 7130156163 9184730305 8310176718 1304866466 9403901755 9500295085 2254984175 5431604236 4531712738 8502396917 3133856302 5316887526 6754801173 5036748623 2398304453 2570813459 3671418400 0181428812 4195883568 6627236523 7858018133 9301903379 1674489503 7479425052 3230173629 5500764209 3728644015 0652441722 7512443463 7925977221 7558978799 3377343779 6303484335 6946809513 6017855294 0749106867 3686969422 3881751731 2105029924 7373526910 5765887414 6343292451 0088738619 3132995005 8958379311 1526816094 5247626027 8587075653 9973644191 9983876644 7205298701 4260870931 0700563507 1659818369 8097793858 0534050430 1581031399 5894516700 1014293723 6542500796 7388369385 6208040108 4750908251 8010039150 5403276345 4909205620 3030592019 5088076504 0230655478 3820955754 4457845690 3913072839 6944996787 1957511817 2311657724 4698239354 4339360060 4615258089 3451000095 5910790033 3628975499 1723438727 3643886907 0188167595 6198030403 6667339064 3465375283 7368563633 2649994807 2941281076 0901635828 3923490430 5986820991 9223204413 4866229944 4958769130 3662771743 2766088664 9624199914 8393639446 9331613015 7810094784 9105432423 9680200204 4549368632 3614777289 2636471023 4580834067 3922208206 7521059962 3299651725 1329169964 0399217703 1515817560 7651813182 0299189381 8502247103 7902325717 0989131471 3880724033 8282144392 9488102562 5920212840 8862360922 5686486888 9133105712 3614015831 8728885895 2141713463 0049067287 0759201777 1570497549 7516732939
• c₂= 3 2986271650 5832184030 8727303277 1491509618 2783984154 8147100107 7711931731 5115767816 7673096365 3091450205 5311316543 9819635933 0580975999 7018571125 7398027541 9692107939 6595524593 6644084726 7634523638 0591638844 5892022104 6246108699 2239386897 9165430682 8510021324 9961049426 1690707806 2558502345 8922207312 1931623761 1641580179 6985759666 7295875664 2887522880 2435948198 8976149295 0880525608 1831031549 4240619925 2645021223 2112565685 4787841186 6435901149 0926278192 5788533622 7321979294 4754234471 5544588465 9289814989 0805699721 4560685494 8944828806 4677410282 5420565786 1656910193 8663336545 4660133085 3286216455 0777769819 7518729603 5938826747 3007370983 9109118411 2826641643 0254608996 5714673700 1664511276 5750668594 7103796465 3354186150 0884946843 8738035361 6624106516 8864180822 7816650834 5352900766 3047560061 4764519832 5191734991 7062477543 7146952392 4937594699 9942457691 0702689753 7026711007 3882983974 3678056569 8148142819 6415737149 1822103515 8133478339 7025465386 3432332602 1844105915 1836250709 9757552027 8763647475 1524395516 6270989257 6886431052 2512925870 8755485570 3774488904 2536424826 6950029455 7870748795 7123635001 9070366993 5515940776 6728920594 0953659118 3790833721 0835681358 8573160498 2170293933 7898100943 8032021505 1883396709 8551519281 6965830687 3694696654 3010665215 7604631685 3508202786 9286165366 0966651521 7512121894 3007250522 8425016243 9652169898 2180834848 9300925584 6888320065 8592124791 1027103863 2516170131 9667597481 7521602917 5123634450 7380101489 1882413535 3531339504 3290003995 8925015287 2505397292 1336774405 0381349891 3230203183 5867003901 2413116382 6612106274 7246101829 2588852044 9527277680 1380680893 7590527838 2847045714 2190017255 8639580742 1738602139 8426946734 9473007540 3078116980 0985933148 3297311998 1034695189 3540409319 4993133293 9465361753 2963354526 4938900612 4547768836 5547111911 6475327200 6674521260 8627624630 4101223329 3338328679 3493529337 9645664951 9517914732 5077152184 2085937696 8187854899 4073332122 5856474457 8331891156 4700122991 5545057953 0229270952 0924860164 0775144868 8261558775 1514253139 8706715472 7550518342 3215731046 0388214682 5917725161 5589746259 0702326189 1686247063 9775959477 0139464638 6809171283 0526656247 4952848416 6803116243 1848739221 1131668459 6784149330 9170145636 2477848342 7309865418 3732723035 5800937063 6418809619 1496720933 5716300446 2134232207 5186745428 3739076470 4446333852 5461933756 5527693268 5573663933 3405208056 5227837008 2370943451 9878683850 6294560834 8534204690 0067008456 8059280237 1873390592 3576956731 1223224668 7798341285 6240551174 1630936882 4470160846 6730350282 2992996151 3162037861 6731872464 6826367392 7087108445 8131067344 3602659741 0966641804 1719881358 1657872282 3202733482 1315067192 8902265634 8333385216 5677519370 0421207956 0544229294 8661378665 8598802657 2714270841 5569025148 2301677799 1494796620 5363520796 2118544191
• c₃= 3167 2607475429 9718566195 1013845213 5655687251 2026576100 8372236442 7490044198 9685327984 9329792674 6561149587 2832190287 5697883113 9143012408 6300156247 9991610102 4779169979 3812490245 3009109070 7335705597 5410072625 0747001806 8297110655 2031447295 5273486661 7688858080 2393042091 2826499379 6322841101 5756309438 7231905909 4003687897 0594699234 4729528332 6855234080 5197926001 1545936336 1251421566 4435055774 0526960230 2289206588 7517080901 6279372180 5931267927 6617887631 7824658028 0103999572 8728966580 3107325623 1463898308 5824687974 6952325538 3254929522 9693858766 6516372670 4884949069 7271977004 6232308326 8787826308 6138960217 1076399030 6852326570 1136571405 7546513303 7393866603 8576512084 9093609545 8136683385 8264317082 0396776129 8211789737 8361732095 5677213108 5135456345 6992357699 7396409602 0744645822 8135680766 0277875060 4943745059 7752463961 1052369903 9092332297
• c₄= 14026 6971510820 1743428407 8618869504 6388789115 9280792945 1829581354 8561160373 0745463505 9724806021 6761063843 1028706674 6889615946 3279317830 2136567973 7848214199 9272541455 8863873345 5618861109 3555862879 1577865502 5857047103 6298621751 4330696000 4781420583 8674335103 1394241188 1578964141 5919831166 1312798099 5769548339 8467501043 9597456270 6309191829 0346566222 0530017528 2813178401 2460289979 6091145028 2587767727 5039228004 1427239426 7188065897 0888092561 3788132810 2138757884 5092294741 8818469999 8340540267 5434156413 2096007436 5287693288 1639250045 8979515137 6655648882 7945759544 2347792876 2255962892 0953826711 6511454779 9805595562 7610891251 1531763833 5643685852 0713056537 7519358429 1152661354 0678383786 5570207055 8225934996 6719970157 4828997884 5690019533 1134639198 5971500412 0147027901 8358475329 8082981242 4746193448 2390672183 1889531028 3927142466 2308336822 2236040050 3493434871 8388859701 6785076582 4960818213 5282903975 1973402926 7743505167 8626848071 7830455978 5259091723 4588572532 1891855722 1117784660 3149111595 7352782298 8445412574 7307186431 6299423288 8024846659 9146641120 3721514814 9307745180 9660515493 5708341848 0389954322 3972189226 8676045103 2398849249 3580727460 8282309323 4014279477 0929749978 9024209261 0607157611 7948833131 9209686428 2111944640 8235577012 7643537903 5441092299 4426988847 1541934429 1278504192 3982330586 6256999611 6019845155 6163338989 6786354722 7289950870 6959217069 0170354622 2526833015 6128552691 5694372447 1397410040 7929003217 8169538266 9375962442 4719435817 7863881562 0216559664 7913304562 5797673567 3924105407 6950477793 0149586409 8038474674 1010636872 0869940905 9404103440 4930398449 8634176338 5162353162 6530483069 7510100201 8300907474 1251349238 5699712045 6332670159 5247586151 4696394774 6891996786 6092539405 3712949616 5939278777 2830844271 1833352463 1200163080 7003686982 0832253904 3259386506 8908934887 4569466368 6893731781 8174378829 6195797441 3006681253 7715889382 7649019891 1591007426 6799693837 0160445491 3112276168 2269319184 6327137970 6632195512 1111630400 7188810578 1343939288 7463710016 6120281010 9640109407 9013206153 4622227723 4843742629 9897675380 8412095907 9821772858 2589721555 0022702437 2275119349 3365742904 1079874602 0043741314 5514877204 2059374803 5965540212 6388391599 2595327040 4769723783 0519234988 3925823075 0859945484 6364416551 3946265340 7259413659 4488620621 4397079364 8009643981 6556935992 3946251503 8913365647 7697775573 3651689796 6697795017 1675690840 3909181808 5762436367 6808593090 2450951837 5133928223 4635056717 0912479995 9966616973 6821417953 4497231385 6097225759 9731269365 2014231859 9242780024 9010267281 5897407635 6992056172 6147964583 1274737968 0301085863 8416311493 6986958736 2464960856 2870123615 7546490922 6387853660 2479190849 4115192765 7641908090 8998370818 8172461787 5053101697 5438085263 8875457504 6736238922 3889453361 5760560898 6045675677 2511112468 7276314379 6720955694 4311427359 3862608597 0302839625 9022313100 5702999030 4377996214 3286356296 4830240944 6149262533 9290228685 5346119376 6125600014 3308019124 9490080124 1385463851 5782894465 4125846439 2064797980 4965070560 1897397402 4696072528 8778330711 7065095153 5789840122 7122704912 2910337368 7911666595 9401916119 3682039942 4319787008 2725406762 5904150624 6561426352 6891004005 8444656000 6279646551 6769997349 8607253969 2745120504 8458294344 5801020522 6531152461 5009701095 0426216787 8798582538 3633329538 8240343161 6392170337 7844216757 8782539844 3000442093 2983755606 6188147986 3952769446 8893774259 5668739488 5874158320 8338319618 4284588674 0777497026 9668628112 6491451100 3471432698 9360862494 5860199526 6996608178 1669556301 4966606097 9668343841 5939229051 8840759112 2873451045 2283634312 4572785164 0451454035 6740720039 5914958441 3755153327 8656598191

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 64)
• Q(1) is not a perfect square: it is ≡ 31 (mod 65)
• Q(2) is not a perfect square: it is ≡ 5 (mod 64)
• Q(3) is not a perfect square: it is ≡ 23 (mod 63)
• Q(4) is not a perfect square: it is ≡ 13 (mod 64)
• Q(5) is not a perfect square: it is ≡ 31 (mod 63)

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 = 3739 3308421440 9630760241 2647548987 6539527231 7956172582 7782432766 2260499135 7526983995 9191146768 5159705455 0505089885 3568816853 2191715259 4436129195 1326998350 9474464143 5189514743 5630062972 8541518117 4990384503 5187242635 3726459573 2702908465 2589112481 8284474453 4273462504 6251678281 3695126973 1818369531 6263484485 8414033518 5379414069 5554553342 9025014844 3680712152 1415427240 6653780422 4714788443 0660349782 3897880448 3717354006 1103611899 7370398914 9400815859 2304229242 2882967406 6933790008 9706655160 9452526245 4907487289 1162590435 9125308064 1710177225 9173945622 2809837130 2157638654 4187067232 1630299384 9589358324 7992523808 2395225692 4373327153 8900818302 0870468067 8406621306 6700074381 0910224993 7607310178 4138876986 0087748821 0112128299 9322305388 5463860917 8188944328 6179686017 0900518149 3554040846 4687692579 1158046830 8304820773 7070930726 5237683839 7674136949 2869493310 8039246867 8751334724 7428874955 6915192037 1507566335 9694958873 1959766202 8943749737.

With those constraints, the unique continued fraction is: {0, 6, 2, 1, 1, 2, 5, 1, 1, 1, 28, 1, 2, 1, 1, 1, 1, 99, 15, 2, 10, 3, 1, 39, 8, 3, 1, 8, 1, 2, 8, 4, 1, 111, 7, 1, 27, 1, 1, 2, 3, 398, 1, 17, 1, 6, 1, 2, 1, 1, 1, 1, 1, 1, 3, 8, 419, 8, 1, 1, 1, 6, 3, 69, 3, 1, 2, 1, 4, 1, 3, 1, 11, 2, 10, 3, 2, 3, 2, 3, 11, 5, 8, 12, 2, 1, 4, 2, 5, 1, 2, 3, 5, 7, 3, 5, 1, 2, 2, 1, 1, 5, 3, 1, 1, 397, 1, 1, 28, 12, 9, 78, 1, 1, 14, 1, 1, 2, 6, 2, 2, 6, 1, 10, 1, 1, 1, 7, 1, 7, 15, 1, 6, 2, 1, 1, 1, 6, 2, 1, 1, 1, 4, 4, 1, 1, 16, 1, 1, 1, 1, 3, 2, 38, 5, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 5, 2, 3, 3, 2, 15, 1, 95, 4, 3, 6, 4, 2, 2, 3, 1, 1, 1, 10, 2, 4, 1, 1, 3, 1, 77, 1, 5, 1, 5, 15, 1, 5, 2, 1, 1, 1, 7, 27, 3, 2, 6, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1, 1, 2, 4, 11, 1, 7, 2, 12, 1, 1, 5, 2, 1, 3, 2, 4, 1, 5, 2, 1, 1, 1, 14, 3, 1, 14, 1, 6, 8, 1, 1, 4, 2, 4, 2, 26, 2, 1, 1, 1, 16, 1, 1, 1, 4, 8, 1, 1, 8, 2, 3, 2, 1, 1, 2, 8, 1, 1, 1, 2, 1, 1139, 2, 9, 9, 1, 1, 6, 1, 5, 1, 23, 1, 8, 1, 1, 2, 1, 6, 2, 62, 1, 10, 3, 1, 1, 10, 2, 1, 1, 174, 11, 3, 2, 1, 16, 4, 2, 1, 7, 1, 3, 2, 6, 3, 1, 1, 6, 3, 1, 14, 1, 1, 1, 1, 90, 4, 1, 2, 1, 1, 1, 5, 7, 2, 7, 3, 1, 1, 4, 1, 1, 4, 1, 16, 2, 9, 2, 1, 2, 2, 1, 2, 1, 1, 28, 10, 8, 1, 1, 2, 26, 2, 9, 3, 1, 1, 1, 1, 1, 2, 10, 20, 3, 1, 1, 2, 6, 7, 1, 8, 1, 1, 3, 1, 1, 7, 4, 1, 1, 9, 9, 2, 2, 1, 3, 100, 11, 23, 1, 2, 2, 1, 4, 25, 1, 3, 1, 2, 6, 1, 1, 19, 1, 5, 3, 2, 2, 5, 2, 4, 2, 1, 2, 798, 1, 349, 12, 2, 2, 3, 2, 1, 1, 1, 2, 2, 11, 1, 11, 3, 3, 1, 2, 1, 1, 1, 1, 2, 1, 3, 4, 3, 2, 1, 4, 2, 1, 1, 3, 1, 1, 3, 3, 1, 1, 2, 1, 9, 1, 32, 1, 1, 5, 3, 2, 1, 1, 1, 2, 8, 2, 6, 2, 11, 2, 1, 25, 3, 1, 1, 4, 1, 1, 6, 2, 1, 4, 5, 2, 3, 2, 6, 3, 1, 15, 1, 27, 56, 1, 1, 2, 2, 4, 3, 1, 1, 2, 1, 2, 6, 1, 5, 1, 2, 2, 4, 1, 1, 2, 1, 22, 2, 2, 6, 1, 1, 3, 2, 27, 4, 1, 3, 1, 2, 8, 2, 9, 68, 7, 1, 11, 2, 1, 8, 8, 2, 1, 99, 1, 4, 1, 1, 3, 1, 3, 4, 1, 1, 2, 1, 4, 1, 14, 1, 4, 19, 1, 1, 1, 1, 2, 5, 4, 6, 2, 1, 1, 1, 20, 1, 1, 1, 1, 5, 1, 9, 2, 2, 1, 3, 1, 1, 7, 1, 1, 1, 2, 1, 3, 1, 23, 1, 2, 2, 3, 2, 3, 1, 1, 1, 3, 1, 16, 1, 1, 134, 4, 12, 1, 4, 1, 4, 2, 1, 1, 9, 1, 1, 57, 5, 1, 1, 2, 3, 2, 1, 8, 10, 7, 2, 1, 3, 2, 1, 1, 3, 1, 4, 1, 1, 1, 10, 1, 4, 5, 1, 6, 5, 1, 1, 1, 1, 1, 1, 1, 22, 2, 1, 1, 12, 1, 3, 2, 165, 2, 3, 1, 1, 1, 7, 1, 2, 1, 4, 1, 1, 3, 1, 2, 27, 2, 1, 6, 2, 1, 41, 1, 3, 1, 5, 1, 1, 1, 3, 3, 114, 1, 1, 2, 2, 2, 3, 1, 1, 1, 1, 4, 12, 1, 5, 2, 4, 1, 3, 1, 3, 2, 4, 2, 29, 3, 5, 11, 5, 7, 8, 1, 2, 66, 1, 3, 1, 2, 2, 4, 4, 3, 2, 1, 1, 2, 1, 1, 2, 1, 4, 1, 4, 1, 2, 2, 1, 4, 1, 1, 1, 4, 1, 1, 2, 1, 2, 4, 2, 1, 5, 1, 2, 1, 2, 1, 11, 1, 8, 1, 1, 1, 1, 1, 2, 2, 3, 3, 1, 17, 1, 223, 1, 1, 14, 1, 12, 4, 7, 1, 4, 1, 3, 3, 15, 2, 2, 1, 2, 1, 1, 11, 20, 1, 1, 1, 1, 1, 11, 1, 35, 1, 11, 1, 7, 1, 10, 8, 1, 53, 2, 5, 1, 7, 27, 3, 4, 1, 5, 2, 1, 11, 1, 1, 1, 2, 3, 24, 1, 11, 2, 17, 4, 1, 1, 1, 7, 3, 4, 3, 1, 8, 1, 1, 4, 1, 3, 1, 8, 1, 1, 2, 1, 1, 7, 1, 3, 30, 1, 3, 12, 1, 3, 1, 29, 2, 1, 3, 3, 57, 1, 3, 1, 3, 1, 2, 1, 2, 12, 8, 1, 1, 6, 16, 3, 1, 1, 2, 1, 3, 1, 1, 4, 1, 2, 1, 1, 1, 3, 1, 1, 3, 1, 10, 9, 2, 1, 1, 11, 5, 1, 2, 1, 1, 25, 2, 1, 2, 4, 7, 1, 9, 4, 1, 1, 3, 2, 29, 1, 2, 4, 2, 6, 5, 86, 2, 6, 3, 1, 1, 3, 1, 2, 1, 3, 4, 21, 1, 1, 6, 1, 1, 13, 10, 1, 2, 2, 22, 2, 5, 1, 1, 1, 5, 1, 1, 2, 1, 5, 3, 1, 11, 1, 2, 1, 3, 2, 30, 1, 776, 1, 1, 1, 2, 29, 19, 1, 1, 1, 2, 1, 6, 11, 8, 3, 2, 1, 1, 130, 1, 11, 2, 8, 3, 1, 1, 3, 1, 1, 1, 12, 1, 1, 2, 1, 1, 129, 2, 3, 7, 60, 17, 3, 5, 1, 5, 1, 1, 4, 1, 2, 3, 1, 1, 1, 66, 1, 33, 1, 2, 1, 1, 1, 4, 3, 3, 1, 1, 1, 12, 1, 6, 8, 3, 74, 1, 1, 2, 1, 2, 1, 1, 5, 1, 2, 5, 1, 2, 2, 2, 7, 3, 1, 5, 1, 5010, 1, 3, 5, 9, 1, 3, 2, 3, 4, 2, 21, 1, 1, 2, 3, 1, 108, 1, 8, 3, 1, 3, 2, 9, 1, 1, 1, 2, 2, 1, 9, 15, 2, 1, 5, 1, 3, 3, 2, 2, 1, 1, 1, 6, 1, 1, 18, 2, 2, 2, 3, 1, 1, 19, 1, 3, 2, 13, 1, 69, 4, 1, 2, 1, 7, 2, 1, 1, 1, 2, 103, 3, 1, 20, 1, 1, 1, 2, 2, 1, 4, 1, 1, 6, 2, 10, 2, 1, 15, 2, 12, 21, 1, 77, 2, 1, 1, 2, 5, 1, 14, 1, 2, 7, 1, 1, 5, 7, 3, 6, 3, 84, 3, 2, 3, 2, 2, 6, 15, 4, 2, 1, 2, 4, 1, 14, 6, 21, 1, 48, 5, 1, 1, 2, 7, 3, 1, 17, 2, 1, 1, 1, 7, 1, 2, 17, 3, 5, 1, 1, 3, 87, 4, 1, 2, 1, 19, 391, 2, 1, 3, 4, 2, 1, 2, 5, 2, 1, 1, 1, 2, 1, 2, 9, 2, 4, 2, 1, 1, 3, 3, 1, 2, 3, 1, 2, 1, 5, 17, 7, 1, 1, 1, 1, 6, 7, 1, 1, 1, 1, 2, 3, 1, 1, 2, 1, 1, 1, 9, 1, 2, 12, 1, 38, 3, 1, 10, 1, 5, 18, 3, 1, 4, 2, 5, 5, 1, 2, 1, 1, 1, 1, 3, 4, 1, 35, 1, 4, 1, 4, 2, 1, 6, 9, 3, 39, 21, 1, 3, 1, 1, 1, 8, 1, 1, 9, 1, 6, 1, 14, 10, 9, 43, 2, 1, 3, 4, 2, 13, 1, 1, 4, 3, 16, 4, 3, 1, 4, 887, 2, 1, 12, 6, 1, 4, 1, 5, 1, 1, 1, 1, 1, 10, 2, 1, 5, 6, 1, 81, 1, 2, 5, 2, 3, 10, 1, 1, 2, 3, 81, 1, 14, 1, 1, 1, 1, 4, 2, 10, 6, 2, 3, 165, 3, 3, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 6, 2, 32, 1, 1, 2, 2, 9, 1, 3, 5, 1, 2, 3, 1, 4, 10, 1, 12, 1, 47, 1, 13, 3, 1, 6, 1, 3, 2, 8, 1, 3, 5, 1, 1, 1, 22, 5, 1, 1, 25, 1, 2, 1, 20, 6, 3, 1, 5, 1, 2, 6765, 1, 3, 3, 4, 4, 1, 1, 141, 1, 11, 9, 1, 3, 1, 3, 2, 5, 1, 9, 1, 3, 1, 4, 1, 9, 1, 3, 4, 4, 3, 1, 2, 10, 2, 2, 1, 2, 3, 1, 5, 1, 1, 2, 1, 2, 1, 18, 176, 3, 2, 5, 1, 229, 7, 11, 1, 1, 2, 2, 1, 4, 1, 4, 1, 12, 2, 35, 1, 17, 1, 4, 1, 1, 3, 2, 2, 1, 1, 1, 1, 1, 2, 2, 4, 2, 4, 1, 2, 1, 1, 2, 1, 1, 1, 5, 6, 1, 9, 1, 5, 1, 7, 3, 1, 2, 4, 1, 2, 8, 2, 2, 1, 1, 24, 5, 3, 1, 2, 1, 27, 1, 6, 1, 7, 2, 8, 2, 1, 1, 1, 20, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 9, 2, 1, 11, 2, 1, 34, 2, 2, 20, 1, 2, 1, 2, 1, 2, 7, 25, 1, 2, 6, 4, 3, 15, 3, 2, 14, 4, 1, 3, 2, 1, 4, 1, 2, 188, 5, 2, 13, 1, 9, 7, 4, 1, 6, 3, 2, 1, 4, 1, 6, 1, 23, 1, 2, 3, 3, 4, 2, 1, 16, 8, 1, 1, 1, 1, 8, 2, 32, 13, 6, 2, 1, 2, 1, 2, 2, 4, 8, 4, 23, 14, 1, 1, 1, 1, 2, 18, 1, 27, 6, 2, 1, 1, 7, 1, 17, 3, 3, 1, 3, 10, 1, 2, 2, 1, 2, 2, 1, 4, 12, 1, 1, 6, 1, 3, 3, 1, 3, 28, 1, 2, 4, 69, 1, 4, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 10, 1, 228, 3, 2, 1, 1, 16, 3, 1, 5, 6, 1, 5, 1, 1, 5, 2, 3, 3, 1, 5, 3, 20, 1}, giving these values for u and v:

• u= 492 4325238573 7730464918 8558877568 7530408439 3005789988 4768465443 9777579615 6598083640 9906673579 8829749800 7027951803 6855050485 0614783106 8018615836 1056005444 5197210504 0825839641 5607083636 2046394137 1679123008 8200532559 2937468373 6414144654 1714350621 7728259085 9785471441 3837303390 2779769463 9256690577 7398073754 4142836640 9794638009 0492361541 2323101058 6887119327 8235886774 6366782636 9711370327 9933199867 2205780831 3414327287 6237464608 9269212468 6249348203 7403773512 4514716231 4686711753 9945980121 9135789807 2582301271 7352234322 6031193896 2854580757 8099465696 3182216376 8466048816 5936040576 5196897734 0169260299 7860062716 8673370838 7801528055 4635700590 3050246898 2843339654 9198203705 9614036686 2093915110 8869577770 7938710884 0688622517 2480964764 5899018548 6345580948 8999265106 7993632796 0514847081 9643269891 6553545123 5028009381 3682132002 1131160007 4825708886 1324045959 1986262628 3910574632 2967659725 1027827413 2995725260 7453735892 9143802013 4600776107
• v= 3144 4740868485 9808483254 7909892469 3618516270 0613896177 6378782079 1526448825 3686689237 6619820310 8997715059 6587030004 2454098707 8867196344 2721904822 8625465449 6202216895 8866113588 0994147972 6684571316 0559716791 8166010076 6251322335 2855811355 9478434011 3378661033 9832621413 6236735793 8212318638 6163409714 3798655008 7981577199 6077809337 3180573845 9556593486 7179530550 0213219148 8437482934 1954508998 7846637939 9222833084 8160091922 2296736501 2522889316 7496706308 2223576097 9247217758 6918707574 9561104694 8941419260 0394519184 3102655660 1110922969 3797691917 1338492755 4740526168 9611277968 9771554217 3602960999 1417780129 2887642419 4194035788 8138086563 4221172583 2299909349 6603647000 4140171002 8330558423 5871907496 3303114312 1729934259 7179403703 5348031715 7364821896 6717056337 3873647217 5877420956 9287223077 8183659477 1633388097 3556398246 3924621343 2887118877 9438455319 1142722427 5681246555 2612122439 5959981971 7634692657 0388386610 9503637731 8342275187 4811458022

We also need to calculate d = floor(c₄·v/F + 0.5) = 9959369 3469416742 2561522715 4059207546 8105716008 8662254751 3414903535 4863516924 8995045894 1594911794 2999138412 7966693860 6630253803 3646411607 8617834136 4847788848 4355704682 1629294315 4364960631 5616047925 5682715434 9764070573 8859608437 2750351343 3243064233 0402825193 8609921005 0773943264 7732819778 5277068042 3604116315 4355837913 3860793200 3202270502 9158935952 9920208507 3279268940 3549957572 4473947042 3145368758 1429615858 9739860446 3603860071 3568622493 4758942754 2638571071 8905460987 9685608908 1637327580 3391329955 1405553385 1418018215 6217392258 2953179525 6263067941 1168220446 3668550217 2179732023 8229993735 6021930120 9547952677 3150985892 9082839723 5530657776 2738026629 9285857057 9784683834 8012828053 2546099739 9888657981 6688743405 9211039058 4229616854 8398909325 8819596839 5363030077 4132892385 4836048031 0026915326 5156801172 6566881404 9568011071 2285447257 2453997462 7474335145 0449601559 6679886909 9072544921 0420825378 6350295168 2060712126 1875785260 5072144044 1023609316 8813801868 3709468621 9956326457 0991929165 8158619999 0752173286 8751353826 1147805162 9582116797 6604724997 1438592425 3553119227 7801171592 0786429547 7578073167 3949060999 0841328981 4917678104 4098038827 1092594929 1894271923 6676100068 5587716686 5853868386 8008284084 4958748319 5713435038 9053198361 6168659692 0059730364 1487353517 5037138872 9278563996 3994056627 7860726841 7749847119 5518548971 4068403331 8672540703 5636450268 6798785113 1723111339 5838397473 5829174142 0388496198 0906158585 7625440814 3376141900 1235357726 5854364760 9852148607 2037145597 4118147939 4202547620 5509173402 6809457506 7994595323 8037784698 2922568994 2731289379 7664692238 4795140627 6169338174 4365096836 2376193712 7120088337 7981352252 2176208982 2933802684 9521770263 8278355410 9447057750 5171197748 9753362575 7107619242 4828795481 8741037087 5084703537 3350383870 4735845571 5275675698

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₁= +3144 4740868485 9808483254 7909892469 3618516270 0613896177 6378782079 1526448825 3686689237 6619820310 8997715059 6587030004 2454098707 8867196344 2721904822 8625465449 6202216895 8866113588 0994147972 6684571316 0559716791 8166010076 6251322335 2855811355 9478434011 3378661033 9832621413 6236735793 8212318638 6163409714 3798655008 7981577199 6077809337 3180573845 9556593486 7179530550 0213219148 8437482934 1954508998 7846637939 9222833084 8160091922 2296736501 2522889316 7496706308 2223576097 9247217758 6918707574 9561104694 8941419260 0394519184 3102655660 1110922969 3797691917 1338492755 4740526168 9611277968 9771554217 3602960999 1417780129 2887642419 4194035788 8138086563 4221172583 2299909349 6603647000 4140171002 8330558423 5871907496 3303114312 1729934259 7179403703 5348031715 7364821896 6717056337 3873647217 5877420956 9287223077 8183659477 1633388097 3556398246 3924621343 2887118877 9438455319 1142722427 5681246555 2612122439 5959981971 7634692657 0388386610 9503637731 8342275187 4811458022
• z₂= +2389897 8757132842 9106874811 0459684428 3807588587 0322104040 0989282233 0723886937 6384271896 9040945923 4318286181 1454410301 0548358070 3478144056 9787274928 7938689355 1080389488 1150061261 8800448145 8028733771 9415614877 0464557215 4803385718 7115197300 3872858473 6142635203 0296683656 9882492887 7510643204 5078286133 0602825395 2747480744 1962413023 1362818458 9081914078 8812510610 8775952268 9898956302 2636098546 6535396239 4347632967 4479976602 3346838108 5906248628 5733967656 9638819039 7626251090 3944075919 0565355725 4588625148 5262224469 8011181242 2569369138 2931104223 5549727223 2874286111 3380873896 8635899979 0503323398 0840288705 9315248270 6703429344 9814222093 2211496349 9769484285 7912360726 7355613309 2211058735 5339280852 2156546300 1463218246 6263874651 9745569805 5562394204 7543960215 0172192507 5945039543 6156263691 3710357771 5202505822 0613755191 0487665394 2066107297 8046050484 9353082285 9275705783 3717990144 4258900266 8058795377 7819112076 0699407181 8758545197 1138477231 5712220967 6460180666 9384701311 5779020765 6188979047 0114349433 9857390718 7146711301 4133263958 6957063067 3454723913 4788421495 1837954471 9652718284 9871281864 7413479473 0076985821 6431084315 6054144457 2641544985 2790912865 9799706953 9507788885 5479676809 3042873708 8100375217 3352296711 6856972035 6100825555 3965784374 5206974846 3280830034 0272215694 6773373055 8244655856 6044252511 4078445450 1538289320 9685936610 6816298280 4143462381 4708403906 8075118644 1126804139 6739891629 6964727272 3708232758 1910837505 6350199250 1599322287 6101550831 7480425496 5870629219 4579009016 7484811028 3039241261 2310372907 6717023230 4307058747 3962797187 4320903052 3410738588 7585062992 7901506642 3613935113 6602763723 9490794507 3686841912 4031215288 9992492650 6813116319 8172542215 4013102933 7339221615 9182072985 5549222999 8941148694 8861483482 8006807979 6736136147 2462123060 8528287342
• z₃= -1 4098393559 5690592826 0017250664 5466231028 6621212975 6682831912 3331073876 4146361406 3810918059 2425567836 2204038586 8486437005 8432207453 8137611514 5638899585 7214932084 2583962411 2236580178 8846969164 2765008350 8212918306 5950086723 7606710207 8770956441 8316933911 7288654608 5376165998 7368572600 7839487162 5879794580 4878928873 2765954689 6099695870 4982685216 1165913227 3955029501 6786156846 6548396355 1410333173 0377650984 8187061290 2369615240 2651210424 5002928602 7300355696 1522800564 1975835351 2755576982 1170696261 1049489883 4363126075 2362457770 4939186900 3326737830 8727249920 8273444090 1816057647 9263311108 2700639038 4784743674 9461860305 9941524445 8343621723 1900981121 6479624758 5258905891 3426922859 0347233970 7177278960 9604693982 1959776897 4502480171 0484583467 1245971561 2002528085 5623514930 5879364631 1141453764 1544280890 1570614287 3487561479 6708416206 3707572469 2979818123 3937386106 7623822188 2955634724 4928448941 4231888265 4639834379 2396255060 5145197755 6828283582 1323687555 3671546469 6310126094 2190358642 5648768583 3114449161 8737771865 9283508734 1166285641 8127221322 8029823801 4743567718 8374840369 2775729052 7929845986 5878600203 6746179791 9146178932 3328176929 3089011683 5986626856 5563001680 8885953464 9279523408 9462866659 7238544219 5375712784 0751477290 8115180496 2447550434 3989517269 3655886246 3012158523 6212219985 4603347679 9725022617 4395833153 1754097140 4946949615 0514062983 6734126096 2417881372 7734745979 0686773413 2600450821 3619153528 5802262928 9327841517 9426166242 8326724442 6035997365 4564890141 0459771449 1894541734 6510072404 6911240136 6672241151 9486521231 6452841456 7721232083 3902675363 9625186584 9590325180 9605344273 3638116229 7421079403 0997345516 7530676435 3973965049 4569011080 4200816095 7574643860 7193108779 8956213878 8473317085 5795968950 6810184997 5343413897 5038130400 9514905709 1573803984 0551344141 9720382135 7356842068 6552908756 9976232236 8980708823 8667919281 2992219962 4394066220 4137808761 6052936894 0272410310 7051577434 9597308774 4637251970 5653745816 7154212396 4171490220 6489141320 5010755115 1747613045 7533035382 5434584532 0849127831 2516991895 4866695493 2536889824 9870872900 6006874099 2309065105 8384651807 5901474642 1088582940 2772674361 9884363061 5605707761 2511330850 5295711512 6600833260 8928925338 4807485632 0656785059 6170556327 5633629274 1112717337 8660199393 5155525741 4801806215 2631458025 0295805493 5147575201 6033524062 4629674124 7812812554 8323916673 9115131543 1161885295 3409980293 7971285101 4998019177 0901823814 4683448092 1796839935 7592893738 3620955243 8563003331 4318830971 9168035708 7978529003 4444102598 2975211194 3393048779 9669777204 0663115744 7447320318 2672793649 8669811744 0408267241 3362364562 8028766883 3366669667 9705356719 0975660149 4481406705 7968757128 6660187724 6464680693 4671928370 5133296656 4546419487 3044667131 6253775837 7098621691
• z₄= -9959369 3469416742 2561522715 4059207546 8105716008 8662254751 3414903535 4863516924 8995045894 1594911794 2999138412 7966693860 6630253803 3646411607 8617834136 4847788848 4355704682 1629294315 4364960631 5616047925 5682715434 9764070573 8859608437 2750351343 3243064233 0402825193 8609921005 0773943264 7732819778 5277068042 3604116315 4355837913 3860793200 3202270502 9158935952 9920208507 3279268940 3549957572 4473947042 3145368758 1429615858 9739860446 3603860071 3568622493 4758942754 2638571071 8905460987 9685608908 1637327580 3391329955 1405553385 1418018215 6217392258 2953179525 6263067941 1168220446 3668550217 2179732023 8229993735 6021930120 9547952677 3150985892 9082839723 5530657776 2738026629 9285857057 9784683834 8012828053 2546099739 9888657981 6688743405 9211039058 4229616854 8398909325 8819596839 5363030077 4132892385 4836048031 0026915326 5156801172 6566881404 9568011071 2285447257 2453997462 7474335145 0449601559 6679886909 9072544921 0420825378 6350295168 2060712126 1875785260 5072144044 1023609316 8813801868 3709468621 9956326457 0991929165 8158619999 0752173286 8751353826 1147805162 9582116797 6604724997 1438592425 3553119227 7801171592 0786429547 7578073167 3949060999 0841328981 4917678104 4098038827 1092594929 1894271923 6676100068 5587716686 5853868386 8008284084 4958748319 5713435038 9053198361 6168659692 0059730364 1487353517 5037138872 9278563996 3994056627 7860726841 7749847119 5518548971 4068403331 8672540703 5636450268 6798785113 1723111339 5838397473 5829174142 0388496198 0906158585 7625440814 3376141900 1235357726 5854364760 9852148607 2037145597 4118147939 4202547620 5509173402 6809457506 7994595323 8037784698 2922568994 2731289379 7664692238 4795140627 6169338174 4365096836 2376193712 7120088337 7981352252 2176208982 2933802684 9521770263 8278355410 9447057750 5171197748 9753362575 7107619242 4828795481 8741037087 5084703537 3350383870 4735845571 5275675698

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)
• -2117 4384977650 3608293042 8991444730 9012788682 6464560180 4291409043 0242201594 3212521102 3833685674 4675053457 7091596952 3290985210 5686786397 7856130512 5596826783 4046647777 7809956216 6833584851 6150030050 9003217252 0569019299 4373197025 1825152676 2599026327 2331384829 6483239166 8307057310 8644804304 0389105372 9612047507 8685546761 2706762558 5892389939 8006334379 3987098075 4691962873 7645433431 2902654010 4195629829 7336321452 9464066543 8044518358 5629721949 0763405714 3521792686 1210639183 5823305905 1541468009 0051982604 0839357920 5714923520 1320564581 0855360690 5575498596 1139722734 7284702204 2510427617 5418948680 7963308956 9019505876 4213392508 1646216465 2937191995 8772456117 5858515705 0459198367 8464776260 3136283932 5412919041 1612511217 6057795675 6405601121 2687382666 9076401081 3489637592 8343302128 5190297761 1947551152 9562272810 5933724073 3383447223 1867214954 0640819330 5423009677 5356852642 1290640509 7237888317+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• +2117 4384977650 3608293042 8991444730 9012788682 6464559420 3981119609 3862687411 2679786625 2337962088 5960415120 3565952422 0366819213 6481852070 4947147247 3455179555 6055246011 5056381809 0387961344 5680345414 8788487110 1766558535 2007531894 3079728984 9302507010 4706836022 7704560334 8644991596 2511939032 5335872204 2206908790 8326040777 0636182875 9438853701 0211211111 0481306106 1896241345 3703442300 3548716830 6033069905 5889520475 3680078934 3703499850 9483461271 2457874568 2996711941 9348685230 1751124436 0859339678 0235174195 5366595252 4214693905 7382005087 2327599416 5192022780 7781508290 5203681194 8172550803 8815575192 1476880218 0238327594 7237945545 7401827951 5945814651 3140267693 0175844650 6917446412 1956391920 7844150008 1007830973 8640160865 9840461914 1968295906 1635879300 4943736381 1462338659 2943462014 4992101733 0128657986 1435038822 6560961307 5966634863 9459071829 5152217366 0053642896 2950883159 1233785141 7493378584+ε∈(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.