Primality Certificate for (3031^2753-1)/3030

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.596343% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

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

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 = 3 suffices.

Express N in base F

Let N = c₃·F³ + c₂·F² + c₁·F + 1. Let c₄ = c₃·F+c₂.

• c₁= 23 5395731031 1530221018 5916689876 9163084481 5279724350 4627070595 1431578880 1506536899 0363619646 7011653572 7127093863 5437916540 3279938461 4020353520 1750427635 9300316916 9852497825 7188715258 3363199605 9058593563 5591893689 6741630897 5736093445 3088106349 1721439963 4342824396 5668338815 6463679025 6683725063 6707700294 3864671334 3448395941 9861821705 4680911339 0984572797 1816013993 7286526673 5426195169 4998126958 9528654264 7579493206 8890350188 1446800627 4983781306 6818635473 5668801854 5475694565 7290533550 8922184107 3782623305 3154239005 4015975229 9268738614 1680079756 0618286621 4478095836 4718279103 4969111467 4091699675 2258908179 5027362775 5227281052 1791935414 7078159535 9916910811 2903358514 3876592104 2113812668 7042230056 2231197441 8147786418 0690736383 6596698962 7921299186 4737545497 8711601110 8567116670 4472984087 0788438129 2264515760 7497518180 6585558942 2825779861 3489026387 9266814761 3409349778 9811079740 2299225236 7593065422 0738720389 8636516081 6844158486 9543663938 9036189045 0188033270 8323620714 6967934264 7789216583 2063613244 0539309870 5029344599 7864838532 2498296550 5497016400 3503074929 9187112048 4611876462 9866815186 6422384020 3809709690 3865829921 9376956643 8961657770 3650452521 8815452276 9795496918 5113307139 7465746370 0354392734 8659550439 1364688925 0692461462 0303344550 9713438989 9743524001 5353230572 0552479406 1294746696 6257969553 0677468865 3504325853 4865834876 7437764864 7125737653 2175540182 1412988845 1716274237 1153370641 8275850415 4498315966 7836109487 4228557438 4341914765 8540790464 6190373754 2835653254 4196860981 6376883383 3443860957 4643169188 2373443200 1852300977 6842964198 7261014711 1832018959 6975531757 5678757167 7296400098 4319394450 1876745846 6686641403 8700533309 0874376767 0040138700 7888235856 1708676566 2276327727 8019587070 9202612855 0210277249 2643209778 2577354006 5356805741 2742431722 8730244394 6669557410 9798338330 1823366449 5224442256 3464547602 3458994979 8854354654 9089233573 3244268191 6113602533 1353272679 2200397474 7800593367 7589316910 5062120968 0104768609 9959712572 0450233823 3743130700 7971722169 9162326722 3393666529 3463277121 0759774853 6389203185 9310729734 1724780521 2419315565 2050019493 9063445966 9607448786 9871101055 9241817849 7846855761 2943350953 4763243655 4230121711 4893907730 6442797769 0172631805 8977360414 4952278213 0623174126 3121590490 6856739673 6279559951 8401784308 9589460547 8063971859 2425103499 1327434041 4706094194 4795345338 4722742616 0862518455 2974024897 2594963057 9913088205 2359776961 8398657799 2639846200 5939749095 3558754675 7403891168 8488321018 4761865515 5935499967 9744119128 7104685777 6142033577 5980901902 5880971644 5738356732 8515518233 3289144025 2541108604 5550060542 6093847695 5252520972 9467674086 5349030118 2860253072 7036415869 5527931525 7044776794 2281383089 0944908723 4272941691 8499858664 2963350280 4384589073 0220610435 7840095263 5035606270 3754706046 8158329157 6186639259 8800115316 6485644149 5667783205 2561032111 9668607475 0031542281 0343593347 8780125158 8085580116 6553646232 3703108068 2729929529 2450135627 8551292052 5536221452 4566436361 5695733745 7301312226 4889870957 6520518800 0802307573
• c₂= 19 4606216892 0420306865 1746333398 2694520532 9479186440 6352448677 7119227988 4392972176 4173550771 6398035445 9074318634 3288916770 8578450662 0996651723 7904827948 2729045865 9827382779 8879949109 6967042760 2700580731 4583156862 4065420081 7442645509 2616060089 4053882034 0408437525 2882174136 1409921471 3718691128 5083136985 0768654409 3282111083 2879416023 4223187297 1759774557 9763795937 1044924926 2719964746 5765619919 9462477608 9118129495 8407266998 7777591434 7785098717 6867956364 8601850123 6035100631 1044941807 3492532718 9457077617 1375875749 1652155715 7070685035 4228290007 1557368591 2445923205 5652583767 3704503755 1903161653 6156036636 1976481281 6871279801 8316842518 4304786388 6672328284 8948902081 4799406366 7209958212 2355801306 2716672433 2135393553 3097223862 0854069479 7772917640 3720462940 0431147295 5137084872 1047836506 2569466474 4945948147 7575061965 6832591910 3431381935 0634085014 9295096582 8226539576 6673034436 8889745960 8867179853 5596461714 0298159483 4978998233 6161951002 3495356343 8913881259 1623957733 6145798666 8402987528 2914508845 4247287943 0907864437 7617739490 6330867900 2511096674 5622102996 4820487779 9033977755 2279686570 3721319610 2374181069 1945334792 4536726270 9496150774 6872140718 2159446682 7813880545 8546340909 1753597805 0031288535 9310096731 4800609190 3586218573 9108394376 5198308519 6131862450 6082837366 6977382581 7205800248 6564851475 7323430467 5312757761 9153038642 4584990642 8357168187 2686269967 7352881417 2760030582 4136235078 9376236146 6664720318 9299580232 8581367201 1900696494 6873551152 5949408576 4623282509 6793344258 0025265122 1672057402 3848787882 5384909064 0716834312 0049427710 8687391421 7476724163 0304965627 8114834995 4154459582 4636017967 2699939914 0356681470 2448052804 6709050565 7827143061 3644890647 3190291970 3080651442 7612680703 0480979203 7088903706 0531727874 5939519264 4047928966 5749419811 3256256723 4396022139 9548345937 3468876897 3503590970 3968021109 4121491014 3270338134 2402063847 9710020606 3883107766 4736011605 5224261221 2780764401 1461339949 9900035281 5381745053 7985587057 5482828708 0036587180 9118900340 1726233712 1015843862 6224652293 7949609439 4558950829 8941327210 0310053193 8604695221 0883582530 8926317798 7956588102 4772867736 6206678025 7929573676 8610664796 8407782181 9126156305 6938741262 1852228533 8701642527 4354558164 8989304140 7664567426 0837624766 9168418499 9028291487 8769592911 3386080538 0544747102 5951640113 2764466101 2686593999 4095306480 6638191992 7907331997 4378088262 6774082604 1808475254 4821639622 3289203497 2539082519 4893777839 2876519032 3900372838 3549153344 9133777626 6388064255 3985031267 7715004104 8166819057 9744739489 4110208534 6187785405 1902015662 9392706757 8211012920 0548680479 4973020133 5401915266 4156246297 2707026513 2515859187 7923617167 8893783278 8666495979 2495749328 4053378651 7989037477 9171936091 7206686555 1267435029 7690778936 3161157116 0460683075 4026148154 9632174121 5711258149 5869121532 0842539116 5464007358 2262299174 4510487523 4058615937 4200670520 2999428727 6713683623 0459052982 8162056747 8997386468 0854058210 7843765236 3433429515 8080141620 4063521138 6866195968 8163146827 7298359968 5032547649
• c₃= 5246797 2594509573 1029437793 1907539919 3900365710 9802978123 5570724944 6353712266 5808168476 0392131303 6119031003 6702548230 7559754643 0587092337 6444994805 4648508541 3600014486 6246947333 1952299702 7637853683 3528796581 0025906365 2305028119 9231151238 4521932741 7208469961 7221667506 4218731120 7160543276 6874595384 9172834312 0860178538 1023500721 8920671772 4671101858 8202436952 8773385825 0862194553 3753409278 5536630341 5146748606 6415869411 7101313160 1682145886 7280515091 0080907354 1703530578 8725564302 7803054535 6665527199 5346363922 5886902060 4099315035 9393281972 3049310471 2793904613 8894042916 2901439263 1329503150 1264936217 9186890021 8659096630 0768976229 8556042382 9704371913 3979426648 1685896177 0376938436 2113878702 0282692948 0256592430 2639043931 3525661284 8155828556 0893033153 4683156287 6079195809 1966682891 2782972770
• c₄= 179808238 2529404537 3192341667 6549010092 9039909032 8584826430 1526994508 6409656933 1090165159 3646975774 8476336348 1085232369 9076576790 4044595647 0656668848 3684287220 6635692042 5674489040 0149148004 4352292454 3249651487 2844302419 5495926827 1285628423 0842251005 1232503438 9630020991 5278132752 3441503107 6973436185 8681990964 5707618989 6770283116 5257825287 3817447943 3833672159 0189632140 4601932834 0377788747 4263837387 9485153849 2871738501 1918344690 5772184966 8191303111 4856139458 4769617155 0997386464 8857764849 8444784166 7935991674 0525973611 3745559576 5035954387 6734774554 4971424808 0605870643 8341939315 9550707000 1063892667 7332828325 4844729413 5252677802 3167865034 5610719419 3856764868 8240107098 3860943171 3660510323 8488756372 3727970551 0424012753 1419041400 2633776715 0003155043 5191341287 8584841162 2210747191 4571923444 9268538395 0530153082 6694474755 2017579716 0028980675 9948726168 7284853854 0443630077 6989834213 1565827735 9838476567 0205352099 6827633697 0891596233 2216839992 1975932321 8260315839 9502743482 4154224833 9709789287 0345014429 1137452109 4135860998 4904099503 9831630388 2581242609 1858284070 8414726424 1053610088 4699632736 5087335729 2814311979 4134093669 7134302355 4997934960 5532411584 6437045565 0465538673 6392684462 4728900166 7062480853 8900182401 0362550945 0482398721 1421146667 8359188882 0030829059 8332392050 9248475377 1794078210 1831539934 0679106285 2805144936 2885963242 1099078734 5629289657 6272225107 4477791975 9219557753 9397589411 0797639382 5692901482 6911211853 2831440017 7018231068 2749869386 8466490749 8477547303 4228923784 1236855401 5881872799 3605119466 2549115573 2809609446 9280015655 0880000877 9699917094 8138336786 4104586313 7724269356 2732107844 6813288222 6185528651 8980603255 0710295703 4650175791 3989102094 0128631525 9421584028 5294537876 5023095700 0391192293 6562946923 0002122436 2099396851 5302224695 4500518791 4266108828 3467067582 4483468056 1989637408 9377822482 4988266268 5464361959 7288268209 9432209290 9657346147 3878950620 9714696998 4807450638 0691203316 3362082708 2183725569 4790762482 0825070630 4107963631 9383929585 3902728670 4047895450 7080829434 7399497482 7875336655 3955897250 8205412688 6688084595 7836546167 4854100442 4904484032 0105378560 9103678636 7438417200 1422680114 9239233354 4979135765 3963663768 8254777290 2607798201 2598760111 3529131766 9018377408 6754930123 2929409799 1295392867 4230059803 5746954230 1838181096 6196509856 8046354706 2429993950 2201546750 3005998817 7882162499 7513633116 3895914609 1501490763 6628459026 2841310624 7732733917 5060645273 6497447889 2070833605 6833362831 2672428945 0709424521 7814380161 3186483451 7391225324 7649649869 8838577352 9406092184 3191721914 2817299019 7993344847 9532956596 4868293250 8546421493 8967234992 6849474528 1832257052 0403618296 0554985318 1995104183 7835927504 6231880771 7587355083 7784238496 9728975332 8446071307 9976078080 8388558903 7330280421 0209954812 4308982246 4139719926 1170462777 8883342494 4747310222 3016027058 4596180202 5951940787 9646640376 7727397250 5144120684 7715345296 8637182173 3864670536 4826158416 4878145081 3090873025 0665902849 9166063125 5730010328 1673873209 1891533672 4681580657 6206346416 5851061598 0235968313 2917928911 1139913538 3524418738 2858400586 5283073212 0693980860 8194980418 4941473993 9302614373 5858699088 7613611147 1447599157 3288910221 1131380987 9286236613 3667714961 8548253491 2740458401 1780718128 4846979249 6277671784 3154826464 7664483218 8099280901 3023697005 7397434424 4601780940 6791648566 4164464654 5030702216 8291741103 1170156302 0855891714 1296699956 9697605666 5951560003 1749889778 5584986433 4472255836 4858860121 0717675376 6292365073 2028338043 8309243626 1320160045 8741027338 4639994261 4068982536 0346127224 8350459323 3748743385 2243810689 8742558899 7164324253 2088979721 4050631258 6763981947 0138660577 1352196363 3932954967 0862437132 1502315249 8654732629 7097997595 2202413794 8843776821 6132374715 5336791274 3082693777 0323717979 8556813392 6398553533 7389917166 5890276743 2039213889

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 ≡ 53 (mod 64)
• Q(1) is not a perfect square: it is ≡ 61 (mod 63)
• Q(2) is not a perfect square: it is ≡ 61 (mod 64)
• Q(3) is not a perfect square: it is ≡ 47 (mod 63)
• Q(4) is not a perfect square: it is ≡ 5 (mod 64)
• Q(5) is not a perfect square: it is ≡ 55 (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 = 255 5703748241 1694193488 1348845791 7492892932 6730698017 0141803870 6495383043 0910470748 8477252999 3291920060 6829954329 4343623026 5796859676 3727889365 9399011404 7981470829 8801046399 2556933951 9344375871 4453774233 5181633398 1527370833 6184723990 5339662905 2500548518 6063089414 5529100572 1459731749 6477660657 9805728364 3936802656 6089353239 2007635309 1583721799 8207354697 3776490860 2455937768 3503945128 2375889612 9456862072 6540109007 8243111387 1927052586 0159747204 2837092333 4156042194 3897283913 1132229771 8498604077 5748887834 2390802567 5889528284 0042509967 2090850730 5090587328 0638580175 1231364728 7616751176 7088869372 8546103882 5813237004 9656630366 3645764290 1680822283 2368941567 7993800289 9113663499 7889923256 6181724020 0737857471 4142135330 2141037567 8500074401 7910452987 3077842537 1352948587 9380334441 3634401251 7982190518 9973227876 4178263790 4666657130 7333301103 9783357746 6290988421 1300499065 3242154686 2453228408 7946235338 1520953119 4884750170 5838048247 9212795493 9815851272 1596959751 5067716886 6762690818 3418576987 5913186241 4793041120 1162108359 5813169403 1109118337 8542124156 8675588105 5124413376 6014134297.

With those constraints, the unique continued fraction is: {0, 1, 2, 5, 6, 6, 1, 1, 2, 2, 3, 11, 23, 2, 34, 1, 2, 1, 5, 2, 1, 1, 6, 1, 1, 3, 2, 8, 1, 4, 13, 8, 1, 2, 1, 4, 3, 2, 1, 2, 5, 3, 2, 2, 4, 1, 1, 3, 1, 2, 5, 3, 1, 1, 1, 7, 4, 1, 4, 2, 2, 3, 11, 1, 5, 32, 1, 73444887 6340703289 3212332544 0956237315 6653866157 4906523353 5599042100 5719198337 9885695164 0876666357 0304764804 8757344699 4328492051 3308449503 5774231486 9789689759 1612715281 5805980780 0622891948 5413150123 8762598026 3326935180 6029949049 8164132234 9150470749 0394520861 4872526457 9167754081 3880524617 5086489839 1793910819 2789184477 1803613800 5740055324 9970091363 2613586863 5322454571 3568059861 9848656894 6426367503 1615062413 5966590374 4432831355 6525187792 6034877991 7392029862 2173467555 8425694429 0191157536 7018155938 8218097972 2579531634 4628951546 3735889674 7638245681 9027129518 6033180257 4457265353 7997016842 9467040744 8828236629 1098682739 1061254330 2472910226 8168823559 3403664676 4430410059 1094370393 5962599510 3011024493 9554277934 2289648271 6623139813 3217891466 6294608374 2338166989 6879263725 2468345640 2727933883 9564502576 3518389501 2498108672 6771697553 8198058486 4458713870 9573116554 4924561360 8895234074 1420759927 5593380256 5181570035 7606126646 2691727337 2755334097 8175645445 1000898682 4033340072 3581147523 4325912195 8776437949 3898274981, 46, 1, 1, 3, 1, 2, 2, 1, 37, 3, 6, 18, 1, 1, 10, 1, 63, 1, 4, 2, 2, 1, 1, 7, 2, 2, 7, 3, 1, 1, 2, 2, 1, 2, 30, 1, 2, 1, 4, 1, 54, 1, 2, 2, 1, 3, 4, 1, 2, 7, 1, 2, 1, 1, 2, 1, 974, 1, 3, 9, 1, 2}, giving these values for u and v:

• u= 87 7590958054 7359755309 7573715623 0818366355 6363466950 7805800468 6034222364 9423790975 7021236833 9347686636 7443412502 4074823222 6956478915 2424034734 6717597358 0849480854 7838435727 5188961563 4295320303 0600752132 5818177003 0723150481 0194327128 7491717989 7843120245 4884049937 2981217427 5127401394 3453168674 3302430794 3389644142 0399187082 7213440614 1611575974 8031295567 4722037904 8845876777 2197649147 5184795983 0072164116 4020149673 2325434458 3324524731 0336263251 8087145920 5943233153 4098198661 6628394299 4969004512 7030828584 6481947994 8636423989 5032939965 1086150888 6584316882 4869942852 8033274916 0913199305 5266335691 8798385242 8516797037 3470692743 3510483711 9292365094 2060668049 3476366450 4820978410 2344932893 8100087045 2719653385 7812938793 9265953988 6509716996 4864962666 8474073516 1565314740 6731072500 4893359908 8724512948 1935674863 6407305869 2761028902 1766371164 7944537039 7362289561 5184882480 2537495139 0734773707 4726794133 7986788738 0807441110 0132611486 3607213456 0891544636 6681629630 3241200861 1144086060 1347874388 7760792515 3568732079 3655493754 0767246569 0325221949 0616427693 6119316264 4278251441 2287549441
• v= 127 7641059655 0537163126 2219133424 6174196895 0559830855 9769665323 8065807753 8348509866 7002042432 5403017659 4295598096 8912738549 5416052833 2950956448 2255446984 9579334689 9829603526 2775349720 7733757256 0150064927 4803666422 0558362125 9951870523 1635059394 4432424621 1399708048 4618281359 3779843573 9871527135 1714364558 1001804467 0585916664 3039212848 5824253675 3537408166 5945565929 7095964708 5853784297 2824385049 4204461434 4364147658 2311272790 8114430928 0524039003 7347020951 1996535269 7099388485 9845789277 9385915038 3535913573 0986424067 2573395006 2050560442 4900851153 8979110049 1375176784 3468657543 9794353599 9900422126 7120197041 3869542373 9742024052 0266400075 8183552237 1457617347 4209122062 3950377880 8719394130 2173727579 2597494576 4466347833 1547600303 7647917428 8759464900 8276683378 1952306277 1795653510 7417538301 8330049092 1952191382 6663896918 4414248728 4707247662 3638764163 7047470126 0130195898 7801435797 7427630478 6345207945 6754718533 3613135621 8004546211 5720735161 4847038539 1168235840 8117922100 9153597846 3814376890 6900640682 0693326977 8221366717 4582676511 1441909460 9013994211 1171156075 4070147058 7559690240

We also need to calculate d = floor(c₄·v/F + 0.5) = 670352361 0360152900 0305315852 7035215304 8621497150 9063774683 9004317717 0367585007 6454173471 9667762163 0091745770 7174969065 9700044359 6893583232 8973578558 6768404784 4401357378 1934021072 3130401546 4533517269 0550089391 8032015399 9661360295 5092416356 7957964832 2840968060 8856247857 5386210177 6069468380 8071487311 2249176445 8003352684 1194528165 5270224420 8023660356 2475897084 5339171171 3418324318 7478337312 8856133400 9118472245 6271540249 5093742749 3319589591 2660742695 4744794484 2961811535 5063212237 3574640590 3533392584 1994284287 4009240521 8512296920 3656397967 8128001723 7880045285 6750494455 8986844086 8476281391 6671810560 7839608884 4261221481 7044293248 8699410472 9990069355 1571224499 4303749296 9214306995 2328117012 9087053209 4295340814 9080219279 4371260277 0681700077 8352971041 3221453189 5743841236 7486458605 5133869061 4192017790 3635806749 6937587674 4093091955 7025451735 6255468809 8492766455 0610224803 7709385224 2671932466 6002864158 6991537039 5647720995 9211347960 4669619168 2602842645 1329854637 1259038066 3598127535 8404259333 1482307982 9995077244 3601040506 3287729008 3597643304 6184436976 8249823115 5724727113 3975415939 6934950124 5478527302 6721798503 1317581899 3890074455 4414418252 6686697995 3848415794 8307654098 1071261751 6450476922 5516852404 1005264680 0600569262 5078459247 5693325364 4056140325 1193532483 0844478801 0334033393 5555153374 0078520058 1604236540 2372714990 8922988183 1588885457 8421925276 3715420275 7095645295 7056032429 5478265876 8681182321 7693946675 3575205571 6858572648 7835520341 8509400771 4408920209 0212712560 7629665439 8571243515 4802476889 2100064465 4206330998 2874854404 2547340438 4582678271 7772586980 0943872907 7072842987 7257865768 7220734517 7714920396 1225661982 3875349949 8545043953 8784903136 3755843377 3917698055 1201507735 6356542761 3427496644 8599807345 8800611849 2096163639 9522258089 6804353956 3620621679 1953733181 4903244275 1793895926 4975657460 9475638164 3515701953 8431975088 7865679419 0469778479 2998685032

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₁= +127 7641059655 0537163126 2219133424 6174196895 0559830855 9769665323 8065807753 8348509866 7002042432 5403017659 4295598096 8912738549 5416052833 2950956448 2255446984 9579334689 9829603526 2775349720 7733757256 0150064927 4803666422 0558362125 9951870523 1635059394 4432424621 1399708048 4618281359 3779843573 9871527135 1714364558 1001804467 0585916664 3039212848 5824253675 3537408166 5945565929 7095964708 5853784297 2824385049 4204461434 4364147658 2311272790 8114430928 0524039003 7347020951 1996535269 7099388485 9845789277 9385915038 3535913573 0986424067 2573395006 2050560442 4900851153 8979110049 1375176784 3468657543 9794353599 9900422126 7120197041 3869542373 9742024052 0266400075 8183552237 1457617347 4209122062 3950377880 8719394130 2173727579 2597494576 4466347833 1547600303 7647917428 8759464900 8276683378 1952306277 1795653510 7417538301 8330049092 1952191382 6663896918 4414248728 4707247662 3638764163 7047470126 0130195898 7801435797 7427630478 6345207945 6754718533 3613135621 8004546211 5720735161 4847038539 1168235840 8117922100 9153597846 3814376890 6900640682 0693326977 8221366717 4582676511 1441909460 9013994211 1171156075 4070147058 7559690240
• z₂= +3197577 4872501357 2868395010 0210000432 8910700514 8043796385 8738596893 5741903838 6611042548 7282863862 2055152695 5440790973 5168512629 7555253310 4155465847 9570495775 6867915667 5418939709 2741732656 8169962068 2839348478 3579205782 9912368879 6770854304 1226773129 6731890455 8438559266 3203947997 7008984104 7390017329 7344909889 3769247956 1469712988 2135268415 1858247202 1139927504 0550399682 9469441804 0497628299 6543701556 5589052990 5670402091 7284487216 3688330319 2782629696 0964237261 1586501945 8566746618 8138922218 0571975139 3978785336 0390501426 3312770196 3341052672
• z₃= -16 2464221545 3295806959 6311650645 4855769641 4690977674 9094934779 6312117745 6013948987 0384204061 1715022732 6677405639 8656637536 4585688664 1412539335 9113982248 5996454569 6546580341 7582323171 7430088845 8167085685 4193733796 2994162807 5148459438 7721525467 1682698140 0291504278 9638336249 5089246861 9469087004 2434400040 5497341620 7937697074 4668542268 7215878855 4722739985 5789561592 0717218414 0721525767 4756607826 2172761271 6118423121 3917617958 2559882649 8371918689 2104770184 4019859952 2003983324 0017632304 9484327378 0853486326 7871232124 0587440820 0625609426 4755596277 0335888672 2682925161 3984950471 2864940198 3800770263 4275167874 9358354364 2551925909 1725718709 8485217102 8854953999 7671631548 5232338597 3886420366 7847827884 8358329299 6679527397 4775094449 7879820582 3038092128 0612352505 9231607407 0832733490 6231251779 9627944387 3235682095 4443230456 5122375173 7740495901 0115333251 1416112876 1889075108 3980587358 9143307403 4417282851 4714037668 9107695610 6251883367 5074543401 2358448782 1220689216 1057422328 6377741430 2063785821 4504850963 4873254298 9093133868 0588067854 4321746357 7464956885 9811245425 0188473936 2001808401 4761179694 2588081526 1374020373 8312646858 6935068092 6501437149 0047341799 1194344708 4759888489 2036182752 7407177029 4939867380 0650215173 6588236865 4706798995 7624520134 7159118739 2548472496 6694166443 7870118559 7329892967 8656310317 3232439557 4832907308 6738735659 2643719535 1741433438 1576448105 5371068215 8265110913 7464733621 8899260898 2722866367 9140544788 0512697788 4651916356 3985018891 5593793276 4216479081 5597748783 7826528624 8602641755 5267932992 4367971511 3056597274 4088256294 4902221553 9344870940 0484306101 8004100879 8959721523 1887192698 7826562899 9492362841 0411697060 9492843585 6790423979 2636906276 4201705892 0510380986 2952251993 7950554162 9051003663 5744424072 1557366582 7228765184 7843677252 5066093600 1662470164 9015941146 4005714116 3316551133 4849005544 2382422791 2069989825 5167647314 7345544993 4218335905 1909845767 9750269909 8448564805 0917463592 3112710217 3184112361 6927063913 0220992992 8267081103 0869853138 8915030221 4955047578 4623477596 9642547580 6597287708 1509401315 3972830403 5066008001 6990783183 0467495833 1098804940 9265992356 6142717234 0765818826 7087391389 3523651750 7467357552 8103043215 9356125867 6362046283 4526709839 0870081420 6769812265 8234165765 5141785877 0581804530 0034172975 8341830700 7407621755 4758182156 2624806368 8571582883 9111950151 7076601718 7116623859 0063687888 5252472690 1866660957 9806667354 5675232926 4242061165 6346009073 4233792443 0883350457 6563738337 7185627561 5260808926 6722201797 7949033865 3856391175 5489320443 5315565366 1473066354 8373749892 9774924200 4346079457 0064596248 1734622195 8629253761 7260692621 0937699800 7355955246 6365085237 7236637995 2634759683 3805465092 8886397577 2264700970 0551984477 3724323631 7128415714 3940328614 7802630035 9679384125 8058849679 6244585329 7387197280 1656270871 5449686526 8046948068 7443755563 1613358770 6201004592 4523912693 6212114638 9048552774 8292646026 5376104171 3701794013 3486658883 4592031257 7624024831 7946737685 5733188025 1697751037 6653296967 5006616572 3754256383
• z₄= -670352361 0360152900 0305315852 7035215304 8621497150 9063774683 9004317717 0367585007 6454173471 9667762163 0091745770 7174969065 9700044359 6893583232 8973578558 6768404784 4401357378 1934021072 3130401546 4533517269 0550089391 8032015399 9661360295 5092416356 7957964832 2840968060 8856247857 5386210177 6069468380 8071487311 2249176445 8003352684 1194528165 5270224420 8023660356 2475897084 5339171171 3418324318 7478337312 8856133400 9118472245 6271540249 5093742749 3319589591 2660742695 4744794484 2961811535 5063212237 3574640590 3533392584 1994284287 4009240521 8512296920 3656397967 8128001723 7880045285 6750494455 8986844086 8476281391 6671810560 7839608884 4261221481 7044293248 8699410472 9990069355 1571224499 4303749296 9214306995 2328117012 9087053209 4295340814 9080219279 4371260277 0681700077 8352971041 3221453189 5743841236 7486458605 5133869061 4192017790 3635806749 6937587674 4093091955 7025451735 6255468809 8492766455 0610224803 7709385224 2671932466 6002864158 6991537039 5647720995 9211347960 4669619168 2602842645 1329854637 1259038066 3598127535 8404259333 1482307982 9995077244 3601040506 3287729008 3597643304 6184436976 8249823115 5724727113 3975415939 6934950124 5478527302 6721798503 1317581899 3890074455 4414418252 6686697995 3848415794 8307654098 1071261751 6450476922 5516852404 1005264680 0600569262 5078459247 5693325364 4056140325 1193532483 0844478801 0334033393 5555153374 0078520058 1604236540 2372714990 8922988183 1588885457 8421925276 3715420275 7095645295 7056032429 5478265876 8681182321 7693946675 3575205571 6858572648 7835520341 8509400771 4408920209 0212712560 7629665439 8571243515 4802476889 2100064465 4206330998 2874854404 2547340438 4582678271 7772586980 0943872907 7072842987 7257865768 7220734517 7714920396 1225661982 3875349949 8545043953 8784903136 3755843377 3917698055 1201507735 6356542761 3427496644 8599807345 8800611849 2096163639 9522258089 6804353956 3620621679 1953733181 4903244275 1793895926 4975657460 9475638164 3515701953 8431975088 7865679419 0469778479 2998685032

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)
• - 3565943327 8476900460 2657440294 7612017935 9402117274 9999051633 0574940626 8737907095 5054286073 4557333168 5097121313 8263490421 5688261452 1417312192 5720446212 1145420131 1921336905 7465275002 3418668667 4474677404 3654095744 9731149909 3677539689 8809562224 0723376544 8505802912 5422597715 5231238230 1861707182 1781030200 5299504779 4886071519 2717749927 9195715663 8192218056 0227055380 1089453546 5151248234 9767156510 7765442761 4943689782 9023367072 9564924314 6949809160 2528926746 1564015716 7700404396 4704703040 4819875106 0469687676 9001257110 1321094184 1600629164 7968895328 5350021878 0432897765 9658594287 4380322174 9363778421 7542174431 3196621785 3636744310 2653612261 8143771076 1181878124 5982927491 9653470066 8899710321 8146452494 7488847999 9193050615 5352747324 5444271800 4135253393 2470172147 3004450952 5734061689 1766573447 3423740058 8255349324 6891666486 3459648295 0295534915 5887534164 6349772893 4876728152 7226185766 7389919273 4581575643 7312573113 2079896612 0580790318 5690683471+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• + 3565943327 8476900460 2657440294 7612017935 9402117274 9999051633 0574940626 8737907095 5054286073 4557333168 5097121313 8263490421 5688261452 1417312192 5720446212 1145420131 1921336905 7465275002 3418668667 4474677404 3654095744 9731149909 3677539689 8809562224 0723376544 8505802912 5422597715 5231238230 1861707182 1781030200 5299504779 4886071519 2717749927 9195715663 8192218056 0227055380 1089453546 5151248234 9767156510 7765442761 4943689782 9023367072 9564924314 6949809160 2528926746 1564015716 7700404396 4704703040 4819875106 0469687676 9001257110 1321094184 1600629164 7968895328 5350021878 0432897765 9658594287 4380322174 9363778421 7542174431 3196621785 3636744310 2653612261 8143771076 1181878124 5982927491 9653470066 8899710321 8146452494 7488847999 9193050615 5352747324 5444271800 4135253393 2470172147 3004450952 5734061689 1766573447 3423740058 8255349324 6891666486 3459648295 0295534915 5887534164 6349772893 4876728152 7226185766 7389919273 4581575643 7312573113 2079896612 0580790318 5690683470+ε∈(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.