Primality Certificate for (7888^2011-1)/7887

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 31.905446% 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) = 31.905446%

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

Express N in base F

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

• c₁= 1027341746 5348041423 9459800442 5535686283 3788779160 0402981980 5605060499 3953252680 3865542094 5519067302 9723479055 7920305113 3764210125 3383125065 4937132725 4564497633 3081429402 0375099460 5324417946 4062061103 0026800683 5636690254 6036162344 5688368390 6172450290 4595841562 3525938798 4159033491 1435625082 8074090584 0214920638 2177298068 9178596472 6030508869 6699544593 1082198924 1808050429 9239838312 8333900226 8947781230 3352369655 2951418484 1955220330 2558253393 1424190847 4231140695 5876787081 7523262316 8714307398 8205069617 0983080600 5472963830 4450346238 2297922764 4166214943 6228011772 4054687646 2865233424 0117490595 6013696890 9240088884 1874154508 0165308967 5932608016 9838874771 7411104819 8177178852 1712123435 1749053950 0977894540 5229201529 6226687594 7878874827 3847903629 0655196952 7348963953 8956110240 5550550928 9309472942 1288672695 1778202185 1109213727 6566673851 2587677744 4573687299 8696360864 6931705909 2286585757 0530161848 6435371662 4234922410 5259692933 3139045897 4219035935 2074657036 4605609273 3766006884 1061964536 7079874605 0167164217 2828819678 4480217153 4239275585 1043581057 9531638699 0885144970 1890816820 8901945305 8089710502 7409078393 3498135496 7195400464 6947539647 3493468466 7248938064 7358068706 0696627008 9339580874 8998847554 4793795824 9657251004 7334341875 3179884217 5521990113 2869939694 3908230090 9420404324 6474622907 7332229880 5744826809 4502775386 3541099428 5988364936 2422720233 2936983284 1639090826 5972435904 1843913589 9364371893 1083047864 4921265199 4131338686 3259966497 0070564907 7054065401 5494852759 8336637139 2781425365 9311959308 6920170980 7628388776 7184595224 2870256755 5711490451 4053491978 4533634516 6594231225 3829784380 2208720386 3717587749 7542245332 3935801364 8948855328 4160760458 8669679972 0213823808 0332012104 1323185247 6978503573 1474379183 6644485849 0734650667 1557313571 3263659366 1699298470 9508943363 4471832177 6149190492 4324368590 6024199906 9704518480 5242353141 2093955724 0769983731 2825606945 7180600870 8569047672 5935137069 6077975721 6592222625 5702389341 8121806982 5563287541 7590219276 6655603452 5283795329 0449062639 5386642916 4076860096 5609853402 1401491848 3575958630 8764019620 4328984985 7474317376 5774135518 4026933940 5657659137 9705602632 8981068958 9779281065 3007966537 9896670036 6780238187 7342574085 1137727154 0258220292 5315015132 2314664936 2707908107 7337110701 5170554542 4169508748 9692426635 7005162556 8145642331 3592342964 2754782360 6012810978 2727448700 8545924943 2189614699 9959210277 6631671580 9513234249 0493716459 3252101741 2393710837 2915210269 1058063760 9530708667 7783093958 3160047350 4871180988 0419044483 0443655167 6659833124 7219739280 8327331809 6150753359
• c₂= 319348956 7221155235 6946677662 0883525146 0858549155 7494753880 0188451969 3517176307 6176964668 6251910067 1918306180 5908311023 9481592782 8014047285 5321147098 4120844007 8870968848 1607011075 7943444763 2628964401 9081576536 3704862093 3530176410 4850044247 3476955880 7815474047 2188031985 6562434913 9069238628 1228170782 6726973126 7132640962 3116116764 3105388111 0687202216 1986611949 0111333881 6816787213 0163249540 4632065632 3079860535 1059704558 6995264866 8603263765 5097254205 9171445598 9136967107 3895036599 4434702379 9398144303 8758454197 8303570593 4508741670 4395151121 8803140037 5961765145 3494398784 8769302916 4603279700 1819764807 3197354840 5400239103 9216113523 2474841384 7553396096 4644527449 6462089456 0666744517 3158996387 5978636794 2408930593 6885687894 3929092100 1847936823 9178824651 5789738178 1163245719 1931686515 2713168943 4963487134 8880711096 2810049856 7654867494 6273321567 9015833689 3919586652 0518066550 1461436943 1270449046 4693012740 7662890691 0447002824 2043467213 5056675534 2671542117 9087492286 0109906817 1350333343 3038834936 1634673765 8925134704 2264929727 5957176651 9756316363 2806494133 4263133212 9786215733 4371003885 5293960218 1374768095 4759006046 4180743032 4896062435 3973664555 2740789158 8292796646 9528689360 8527289517 5019901531 3846908396 1882440944 0869451511 9437129008 9437296873 4053745266 3756925025 3543991004 4708453659 1235985689 7494459662 9868235349 4240833593 5246628344 2369115944 7330358692 7353912267 5746932916 8755006363 3176195281 4688420401 1803870393 5295524275 2717360058 8384402111 4189855721 9534072386 8651144881 9235516802 6242802497 6508883124 2844139504 4165906894 3274193500 9230378927 5978157066 2431219309 4175145799 3054698282 4594988748 9503100918 8439001753 6524415425 5314658083 8395368637 0650345527 2432376684 5203221425 2070168716 9526759181 1267733204 0711901924 5202888341 4516247950 0981312792 6196514372 3358458458 3514220152 0713209174 5098142452 1567978964 4308840318 1497721699 4818238767 3496268857 6678609633 7573251517 1355494343 1403274640 4046112733 7457407362 8380160290 8470340400 3612329120 3948588150 4053916858 9988284640 5463637571 0467989271 3424684089 2248123965 6006372096 6234094000 5594433904 9964091592 0106446198 8523689835 0105343464 4009684288 8884238742 5905312581 6039602186 4294532768 9770649702 7017956169 8963327027 8231381905 2825869389 1546318019 5311873879 6282755289 8889179901 5717130899 1012201757 3429540720 5166750686 7107962750 7112946584 5561132149 9581960086 5087385057 2625500211 1149083286 8753940806 1602141397 2698004981 3840055272 9717353942 8631451599 6462373962 8515637418 9900432756 0185050139 5427527670 0511724308 9446785680 5232063695 6729773198 7428739893 2308101595 6780158014
• c₃= 342931 3384516376 4868953358 3456374606 0285194794 0525183157 5359421058 7803635200 9992076246 9444333891 8334950005 7729351795 3903804664 4057309446 8397399105 0853352436 0778889391 4198850102 6889959246 4659633996 4524435222 1226968744 2764455835 6481142912 5221910874 2130996638 0548748922 6062501024 2548604866 5746175437 4268512387 1809227011 1684393621 1635705709
• c₄= 45496 7909343722 4563795682 9496402209 4528297840 1569279600 8463301164 5362421246 0038248868 9895063806 1822319664 0852222543 1454068006 5285712726 9971695557 3684435724 8610346873 4244914131 3095307927 7062618771 1026121526 0335492821 6588061116 2194843999 6524291625 0735695345 9595705281 3808770236 7111966920 6074267495 6263001916 4743304426 2807818714 0105069702 5967709627 6692469431 3286714270 7733808100 5379166824 7557370473 3856299252 7609739878 5968464246 6181715202 7634208158 0484651294 6883871544 5045354514 7090533452 7280929475 0998622539 8103431289 8608310057 7595928416 2544296727 0598871274 1626442162 7005890993 3353323575 0409662274 8180218790 1691939254 2887033417 0648064574 3721119156 9997216178 8614599292 2303000364 9192243801 3984834495 7401113962 8624820543 6324241663 6728750781 0122826472 8253714590 2321686817 0890763309 4491784011 3449302702 0019635700 6270165914 4652865687 9617238958 0234531951 0408499795 2513680358 4271074882 0944440586 5747303869 1401748581 9945551577 5419986560 7341810454 7849133187 6148242027 8764159494 0544137184 9956703963 7335817605 0488093150 2977698444 4300924392 6970058790 6589176930 1885015271 3823712098 2660494478 7257690143 4167675528 1994966527 2722037573 1594541199 8348718918 4653294276 2752142521 8741785181 1844825213 9934492726 6082358030 3862132458 4001796672 7226094896 2109546741 1644700954 5120420799 0035415024 3115570247 2510569302 1771865867 8377746280 7421616577 2371252937 0761735498 5179465146 0832852885 3260581320 2509279746 6455425542 1444865222 1333887598 1718781194 1365822597 5314136185 3189235534 8766791329 1844148569 6092327220 4010119786 1247747995 4527095725 0133976867 3396792889 7656553767 9300620698 2893302499 6634113349 5390432140 4225494095 2941014750 9106181199 3603875338 4608373997 0973966043 2563373649 0921433828 2547957940 3529181620 0953683156 3690404117 8296696002 4990072942 4189269957 5559309725 2780471863 2165023923 9889094277 1707150258 6774811910 7558494851 3570918124 5241310135 2877745479 5284423728 1360036967 9201486896 5268928895 9004966241 7912104266 1595787925 6283167121 4438766459 9624697419 4442481173 6226618419 1557766976 5595802693 8286553057 6560552821 3442476107 5652932283 4631182524 0177751695 2652755109 4421168901 4156037162 7707979116 8183139949 6756273875 6631488092 4144958611 3003908749 5608663955 1499075059 4925894789 2064768087 0347593632 5391399478 7470031498 6848620420 2537088854 7767443848 5366953446 1629860844 2028367673 0700561656 1161217436 7462020229 0744018613 1807683501 7071875822 4793892741 7826745545 1878497851 8224722689 9066595844 2048949858 3270297195 9275834381 4587196328 2165118426 5602807479 7606967274 9899472304 1314813868 3022063762 7956817660 5240093251 3865475148 0638073603 6309027869 3507890224 2995056358 6484654242 6326819826 1936569660 2435689780 3687009589 3528166537 8789749720 3323196542 5815091930 5169016714 8008550336 2428303974 0424652390 4976195570 9127337691 5718359119 0695229545 2883057258 9668942279 4303838531 6070664064 0079814319 8015943418 9174742142 3263998614 3522206916 3851877113 2685323713 8441697150 4221787186 0580364718

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 ≡ 24 (mod 63)
• Q(1) is not a perfect square: it is ≡ 13 (mod 64)
• Q(2) is not a perfect square: it is ≡ 53 (mod 63)
• Q(3) is not a perfect square: it is ≡ 21 (mod 64)
• Q(4) is not a perfect square: it is ≡ 19 (mod 63)
• Q(5) is not a perfect square: it is ≡ 29 (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 = 62 1989721737 2708547188 7755570151 5483662962 4882161605 1411158296 5239981851 6220919416 6006902192 3422722012 1951781962 3140942278 4398601006 8878665053 7619473964 5123391349 5211511312 8062893674 4891032459 5187617194 8128897989 4899811667 5996282083 8756945104 5913366152 0234267848 1065669623 7531209585 3242251332 0371835297 3695725101 9061192078 1632979143 3603072402 1592096748 8604368970 9374190810 0539187045 7687862401 8161910638 4257110612 8198078756 7111538240 3154140117 8876459599 7123716193 1089676433 0580179259 6057193529 5518250573 0416538672 8885787360 6100473688 5697561141 8002658518 8224024100 3275940527 3807542058 8272563626 4324584605 1377188327 2773685107 0188252810 7640377641 1977858365 0994006720 3342343883 5881252783 4372913059 3518383427 5502437253 1509249945 3252199000 4516420006 4653730575 2835777957 5744549626 4958240601 9779045644 8655180264 0284912107 0759717390 5823708817 3458804211 2709370808 1573797059 2457574814 0671524611 5930418169 6186982234 7361504606 7720844020 2236981495 6931551769 5289245124 6530327223 8415836821 1852919578 8629829194 8840849379 6888935880 4636884093 5629036228 0725203022 4623948200 5732449912 7514574459 3379296904.

With those constraints, the unique continued fraction is: {0, 1, 3, 2, 3, 6, 14, 1, 2, 1, 2, 1, 8, 3, 29, 4, 7, 9, 7, 4, 8, 1, 2, 61, 1, 2, 3, 1, 3, 12, 13, 1, 4, 70, 8, 35, 1, 7, 1, 1, 3, 1, 3, 1, 3, 1, 1, 2, 1, 1, 7, 4, 1, 10, 2, 1, 1, 83, 1, 1, 11, 1, 1, 8, 1, 1, 6, 1, 2, 19, 1, 4, 1, 1, 3, 3, 5, 22, 5, 19, 1, 1, 1, 4, 2, 2, 2, 1, 6, 2, 1, 1, 1, 1, 2, 1, 1, 16, 1, 76, 1, 45, 3, 1, 41, 1, 2, 176, 1, 1, 22, 2, 13, 2, 15, 1, 1, 7, 2, 1, 2, 33, 3, 1, 2, 1, 1, 2, 2, 53, 1, 1, 5, 5, 1, 2, 1, 1, 1, 6, 1, 2, 2, 1, 1, 2, 1, 5, 6773, 1, 1, 1, 2, 1, 1, 10, 14, 3, 1, 22, 5, 2, 10, 1, 1, 1, 1, 1, 2, 11, 2126, 6, 1, 1, 3, 6, 4, 10, 4, 18, 6, 1, 1, 4, 2, 2, 1, 1, 6, 2, 2, 2, 22, 3, 1, 2, 20, 1, 9, 3, 1, 1, 9, 1, 41, 17, 1, 25, 3, 4, 1, 2, 2, 1, 3, 1, 123, 1, 2, 1, 1, 1, 1, 1, 424, 19, 12, 30, 1, 2, 4, 1, 7, 1, 3, 2, 3, 1, 27, 1, 5, 8, 1, 1, 2, 8, 8, 3, 1, 2, 1, 10, 1, 49, 1, 1, 2, 1, 8, 13, 1, 1, 1, 2, 2, 1, 3, 3, 4, 1, 3, 1, 2, 6, 1, 3, 3, 3, 3, 16, 1, 2, 5, 1, 10, 4, 1, 1, 1, 3, 1, 2, 1, 8, 1, 1, 30, 1, 7, 1, 1, 37, 1, 7, 1, 6, 1, 24, 1, 19, 4, 1, 1, 4, 1, 1, 20, 2, 44, 1, 1, 1, 3, 93, 4, 71, 2, 1, 2, 9, 1, 1, 8, 1, 12, 1, 7, 95, 17, 1, 1, 1, 8, 1, 3, 1, 1, 5, 9, 1, 3, 27, 3, 1, 3, 17, 1, 1, 1, 1, 10, 2, 2, 6, 1, 2, 4, 5, 2, 22, 8, 4, 9, 1, 3, 3, 8, 7, 3, 1, 1, 11, 5, 3, 2, 1, 1, 2, 6, 1, 24, 1, 4, 2, 7, 3, 1, 3, 6, 1, 1, 51, 1, 4, 2, 1, 15574, 1, 3, 1, 4, 1, 1, 1, 2, 3, 1, 1, 1, 4, 19, 1, 17, 2, 12, 11, 1, 1, 1, 1, 3, 1, 1, 2652, 96885839 1428111577 0825178126 6588031579 7621080992 6435917831 3896143920 8116605438 2968518785 5745148972 1635225308 6131023103 6284929141 4504068326 0815004873 0056279563 8161239616 8519745056 7731285033 7210382520 0928785922 7549609385 7328796052 2864865728 1317614586 2570310677 8459589783 2792779234 9422539743 0143175152 6193351957 9327820326 6752120787 3464309693 3038055951 9299766045 2257106339 7482631278 9762129650 5657296080 4494041132 4052822352 2971628872 5032146579 6773405553 6232140273 2118412095 0426129045 2839985811 9863381422 6897626204 0468140052 4897434858 4512806340 5217143112 2570490658 6436296052 6971100944 1204358726 0246327260, 4, 1, 3, 21, 40, 3, 1, 8, 7, 4, 1, 9, 1, 6, 3, 1, 2, 4, 4, 29, 2, 2, 1, 2, 2, 1, 1, 1, 4, 4, 1, 2, 33, 1, 1, 1, 29, 1, 1, 12, 3, 1, 1, 2, 2, 10, 2, 3, 2, 1, 47, 2, 1, 3, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 2, 16, 1, 2, 1, 1, 10, 1, 3, 6, 2, 3, 5, 1, 1, 3, 21, 5, 1, 10, 3, 1, 12, 4, 21, 7, 3, 1, 90, 2, 1, 1, 2, 7, 1, 2, 3, 6, 28, 6, 1, 1, 2, 1, 3, 2, 10, 18, 2, 1, 1, 6, 2, 1, 14, 23, 3, 4, 3, 1, 25, 8, 2, 9, 3, 3, 2, 1, 1, 2, 1, 1, 31, 1, 6, 1, 3, 2, 1, 1, 1, 1, 194, 8, 1, 1, 5, 2, 1, 1, 3, 1, 1, 9, 1, 3, 3, 4, 1, 1, 5, 1, 3, 7, 1, 27, 20, 2, 1, 3, 1, 2, 1, 1, 22, 9, 2, 3, 3, 2, 1, 1, 66, 5, 1, 1, 2, 2, 5, 1, 3, 7, 1, 1, 1, 3, 5, 1, 2, 1, 5, 2, 4, 7, 65, 7, 1, 1, 138, 6, 2, 1, 1, 1, 7, 6, 7, 2, 3, 1, 4, 2, 1, 1, 1, 5, 1, 3, 1, 4, 1, 1, 2, 5, 2, 8, 2, 2, 1, 5, 1, 45, 3, 1, 8, 1, 7, 1, 1, 16, 1, 1, 26, 1, 1, 1, 2, 6, 11, 10, 3, 1, 1, 4, 1, 3, 60, 2, 6, 3, 10, 103, 1, 3, 1, 8, 2, 1, 15, 1, 35, 1, 1, 137, 2, 2, 9, 12, 7, 2, 9, 2, 21, 2, 1, 1, 1, 2, 1, 1, 1, 3, 1, 67, 1, 3, 1, 3, 1, 1, 36, 1, 8, 2, 5, 2, 1, 5, 2, 27, 3, 1, 4, 5, 4, 5, 9, 8, 2, 944, 41, 2, 4, 12, 1, 4, 20, 2, 2, 1, 2, 1, 19, 2, 1, 1, 7, 7, 7, 1, 1, 29, 2, 1, 9, 1, 2, 8, 1, 3, 1, 1, 1, 66, 1, 1, 10, 8, 1, 1, 1, 1, 1, 34, 2, 7, 1, 1, 2, 15, 1, 3, 1, 7, 3, 4, 1, 10, 1, 6, 1, 1, 66, 4, 4, 1, 1, 22, 1, 12, 9, 1, 4, 4, 1, 1, 1, 3, 1, 1, 1, 7, 5, 24, 3, 2, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 2, 1, 7, 3, 2, 1, 2, 11, 1, 12, 1, 6, 2, 2, 9, 1, 1, 5, 2, 13, 3, 1, 1, 1, 1, 1, 1}, giving these values for u and v:

• u= 10 9602728167 3403470822 0330406522 6618262243 8362594203 4229113777 4021896112 3644236929 8011585749 9956881657 5774054466 1685528093 0023864899 8069217458 7486615693 3975423251 7894120559 7875739090 5890666597 8685772846 2980544856 8354114658 9091298447 5356044301 1923989812 1395240284 3510679337 0242408503 4693278879 4850443694 7167503521 8925876077 3745690982 6304406498 1236392641 7776971217 4498019058 5861664881 8521380787 7109857672 0272719631 2568786804 1422400543 1724413344 6135205855 5912356998 0157403142 2801355181 6857943624 9449512421 1307287670 1348924375 7592091526 9365766316 5164854041 6190424873 0126672005 2309272229 3154314079 6288375978 7932226432 6614702689 6971213936 4143344810 0217554717 1086620219 7717711718 1728700475 0595631181 9605449027 0432633402 7301880669 1071436778 7143022854 0214058234 3304871561 6310881980 7692292930 4867278047 2730748236 0318292869 8895118279 1038536606 2515254272 1571817885 2522234637 2590047093 0446114815 0930975685 7812349848 9774075546 0964264029 4692885678 3281145496 4451828875 1454602359 4348609263 1546450762 0521388181 1741536207 8054973112 9904427877 8765009761 4135436383 3449686930 2265162725 0351593825 2275577242
• v= 14 1540269761 5809342810 4462314783 1801511693 9061215882 2764706602 6982561549 9968195224 0491767941 4084820098 5311813331 8774246351 4933231597 2399737187 4357851303 7967911890 2375863491 4311045388 5498290058 8322521817 3293545010 3248490355 8694164987 3812886609 7296814248 0101098175 6363669154 2876949678 3908814963 5508010987 1473949741 9061295924 9104659795 6394086674 8695622382 5715083607 9809410247 9223857981 3778412902 9791257360 0948628275 8724997716 8211773703 8549765110 7523758286 0443640486 5599360074 1559471573 6835457731 1106405103 2798438764 1806862003 3832585235 7417740880 2676560380 1561467095 2855785940 2225222018 9803689581 9284019140 1066994931 6880262893 4322288208 4644962883 0787759225 9439765277 5699828885 9249952608 6021873008 8808735027 2274512474 3899601401 9696814019 6699121542 6815406502 6726594044 3321323386 2020081208 5187459769 4299084334 0813093945 4661966102 1157041291 1124687981 2603442261 4372624170 8609667687 6603032110 3418234034 4477011301 3647218652 6912742351 3270213962 8098119636 1691626946 2594784134 3415383496 9822973954 5544966432 0745274259 1917533669 1981425632 7203789664 1891606254 6046894884 3607867915 6144135433 6471546775

We also need to calculate d = floor(c₄·v/F + 0.5) = 4853859 4154144805 4182914039 8621013828 1796820617 1789518085 3695418947 5592577822 1258889863 5716066466 4988098300 7358914446 2400420830 9654534482 3215720496 1222942363 6801446658 6812939834 5234622694 4777865802 3684782825 5823207973 5616889689 3565805733 3263060751 7563130063 5838361989 4797161211 1866037695 6069751606 6617758029 7458457587 9079458960 3050455627 2563253834 8146319869 5322835298 7815768092 7122670420 8065366677 6841975568 5737192097 9289945840 8049290402 7770416395 6131849424 2322433642 9053179146 9720312520 9986419143 4437864074 7551375433 1230843806 8820504723 4525487278 8194845049 9690785301 2861597288 5600876038 7384983506 0658093970 2564425048 5013674597 9517189962 2916638725 1103615424 7401743174 0417048915 7697744485 0315904409 0643674457 6107237276 5426255437 9166484784 5749817354 8895428148 8786762797 6780729798 7368717025 6555861271 4582278204 3080018111 7386486151 6217682107 5918777825 2580074679 4793640386 3033696747 0197109826 1619437684 1453023255 9942778412 8576886008 6170486172 3918369395 0030853398 9053270987 5277219527 7254567141 0672245509 8402447569 1317501510 4164114091 4662908822 8077045802 5742375227 2959439897 9623687091 1819193214 3123893166 3343612677 2969080588 4221064233 3357518112 0921755890 6588010878 6310121348 1592084209 2141287349 0523316536 6575913194 8485635719 6946126023 0374127367 1509433640 9803399470 8268220156 7514986737 6920204656 9606088182 1270387536 5284721404 8872349734 4240765263 8896742538 4449800028 4454005006 9483564024 9741507433 4610736359 0680904541 8887608884

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₁= +14 1540269761 5809342810 4462314783 1801511693 9061215882 2764706602 6982561549 9968195224 0491767941 4084820098 5311813331 8774246351 4933231597 2399737187 4357851303 7967911890 2375863491 4311045388 5498290058 8322521817 3293545010 3248490355 8694164987 3812886609 7296814248 0101098175 6363669154 2876949678 3908814963 5508010987 1473949741 9061295924 9104659795 6394086674 8695622382 5715083607 9809410247 9223857981 3778412902 9791257360 0948628275 8724997716 8211773703 8549765110 7523758286 0443640486 5599360074 1559471573 6835457731 1106405103 2798438764 1806862003 3832585235 7417740880 2676560380 1561467095 2855785940 2225222018 9803689581 9284019140 1066994931 6880262893 4322288208 4644962883 0787759225 9439765277 5699828885 9249952608 6021873008 8808735027 2274512474 3899601401 9696814019 6699121542 6815406502 6726594044 3321323386 2020081208 5187459769 4299084334 0813093945 4661966102 1157041291 1124687981 2603442261 4372624170 8609667687 6603032110 3418234034 4477011301 3647218652 6912742351 3270213962 8098119636 1691626946 2594784134 3415383496 9822973954 5544966432 0745274259 1917533669 1981425632 7203789664 1891606254 6046894884 3607867915 6144135433 6471546775
• z₂= +10548986 0630153072 0869789962 5992987304 2577365914 6077717891 5895509573 5065886777 4318591036 5219388691 0634117574 8167932356 5174543798 8501208483 5732721124 4108280198 8999840018 5618313755 0533172442 2164364861 8464287146 1559469456 3377058169 0968026783 2408135506 5282556491 0090573200 5161958101 5648053844 9371101483 9246801776 3974389253 2163544718 4356994174 6351616892 9406534771 0602072829 6999343906 2640703995 8104579418 6741222215 3274452840 2580284122 6887895256 8161885550 6388579395 8952456184 6957635016 7048769739 5629604629 9195707397 1368808349 7369680316 3916969573 0138330731 9395146819 9776260242 5111423238 7628249774 1398615209 6891042993 0088693848 3433421727 1817043774 9909568226 4173075659 5096103798 3314458039 4351060209 5151153281 0728849014 0458859083 6977354685 2688822789 4442205455 0411251259 5827328725 9148458627 5768430419 9293175984 6149896426 9121041940 1836440328 3765850428 0692239844 4786432579 0774648577 4558941550 1872463514 4384721462 4155981399 5699711741 6155573007 1567553297 6136903603 4233702828 2530144035 2718212945 9828393148 0582804578 1143273285 6181018564 5874334382 9042041666 1669353221 9166547148 0511431944 5096068661 1222087014 3109514830 8090662868 5768406871 9541594808 6493018950 9975990788 8079975116 6506458521 6065650184 7524412442 6471331321 3388814234 5654559927 0042688148 6965548365 1080129008 0203340346 8011452326 0065827762 8137642962 8059499259 1034197836 3207204181 7966885903 4226374885 5266506353 2510657022 3072943751 5915129794 9786236565 7388906046 0523025659 1334464327
• z₃= -195342012 8452040061 0639195201 2720621324 2752922295 2141354686 3450895766 6606030442 1519276527 5713412945 3431550058 8558602585 5165721163 9569038922 7172951420 3129713627 8797928804 5933349630 1011537346 9585695088 8803245713 8669883349 9105232659 6814421079 5948955626 7027709214 1263737706 1574227132 7119312243 8046443633 6753363057 1024878036 1962326333 6431365107 1277826017 6378875971 8635161830 8032330674 0337519686 6920503191 1723630168 1630374400 7829502916 8516593685 0502038765 9284101475 7151165331 2082529038 1413430826 3154802357 0837001230 5638124973 4102335724 8648273669 4491279028 8572343739 5950610853 4500145599 6344868881 2620778474 3572994439 9254230238 7358540718 5999502455 1733653132 6899933060 3605977132 0717501002 9370042212 3912027042 3933484840 0341118314 1793642963 6315571493 4204348999 5216928636 4653369771 1097474183 1722801427 4737155376 3134805828 1053840674 4416808939 5228834587 9156649899 7059575925 0271189635 3378235071 1906931382 4972791568 3445007468 2158510173 8973759996 2284212720 6325176390 9021900726 6369022069 6280835536 6397524447 9973158094 6256517222 4909487687 4831563425 2727403621 2218923654 1761259623 1832224150 4956353058 9521031541 6623635312 8191127609 4812124320 3682767513 7511883762 7932964822 9011819367 9196697206 2703603268 6868065152 6058030295 5635411647 3832627590 3610590316 6823128291 7657442797 7185908274 7002192728 3709363903 1997374134 2529706473 1237033740 6122556670 8474984637 1232239874 0574394327 8822033171 8569010085 8119147096 1218015293 5426047935 6875048381 4323415125 8357371889 7761035855 4817850509 4256044416 8114230127 9384362739 1183379399 8378502672 7220742245 0286801868 6298059413 3541801882 0116181266 8289284264 3366240676 6171549302 6008929422 2941636348 0111298723 1710319119 7706544487 9256128784 8022831286 7750344268 3903794639 5710541195 1638165238 5586396600 3947814256 8582461198 0827670047 9949726521 6651031542 5344573829 9324910754 8186845415 6973257774 4013763276 6531239270 6311114865 7594006347 8255446048 4437372529 1303855317 9466193409 1222483195 5941688574 2515978726 0865157159 1764705342 8250179259 2540696370 0447878467 7580719497 9235240906 8663206401 4923611382 1610212425 9010549316 5230763892 3739122278 9665422306 9580595186 0321472701 7058302891 7526169789 1249033227 5295187611 2693914226 7429846146 9000058880 5692494030 5957595765 0664403629 3828966963 0776550079 3521912860 8935002644 0202994883 1670233470 8547538834 4037640122 1109295412 8765945804 1780619954 4654492853 7550474512 5792619751 4625514890 7138686746 3074084497 8461490609 9883360810 4229284106 0942888196 3227463594 9504554357 0007682733 9750149860 4896355660 3387868378 4727736169 3788567226 9081953515 4193893477 4053751842 0569015237 4511047812
• z₄= -4853859 4154144805 4182914039 8621013828 1796820617 1789518085 3695418947 5592577822 1258889863 5716066466 4988098300 7358914446 2400420830 9654534482 3215720496 1222942363 6801446658 6812939834 5234622694 4777865802 3684782825 5823207973 5616889689 3565805733 3263060751 7563130063 5838361989 4797161211 1866037695 6069751606 6617758029 7458457587 9079458960 3050455627 2563253834 8146319869 5322835298 7815768092 7122670420 8065366677 6841975568 5737192097 9289945840 8049290402 7770416395 6131849424 2322433642 9053179146 9720312520 9986419143 4437864074 7551375433 1230843806 8820504723 4525487278 8194845049 9690785301 2861597288 5600876038 7384983506 0658093970 2564425048 5013674597 9517189962 2916638725 1103615424 7401743174 0417048915 7697744485 0315904409 0643674457 6107237276 5426255437 9166484784 5749817354 8895428148 8786762797 6780729798 7368717025 6555861271 4582278204 3080018111 7386486151 6217682107 5918777825 2580074679 4793640386 3033696747 0197109826 1619437684 1453023255 9942778412 8576886008 6170486172 3918369395 0030853398 9053270987 5277219527 7254567141 0672245509 8402447569 1317501510 4164114091 4662908822 8077045802 5742375227 2959439897 9623687091 1819193214 3123893166 3343612677 2969080588 4221064233 3357518112 0921755890 6588010878 6310121348 1592084209 2141287349 0523316536 6575913194 8485635719 6946126023 0374127367 1509433640 9803399470 8268220156 7514986737 6920204656 9606088182 1270387536 5284721404 8872349734 4240765263 8896742538 4449800028 4454005006 9483564024 9741507433 4610736359 0680904541 8887608884

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)
• -371499145 9945749054 5480599540 3892267255 7108108552 5908025085 3550322568 5645200317 7619816404 4884520496 0295551239 2580609479 3288654204 0997766392 5221949283 6555667804 1085140909 0510886314 5014362054 3565641245 8499057440 1638437428 7038903331 0055860281 3139288787 1720267659 1048044096 5243630719 6631802091 1211511030 0253983712 7286402056 4185357013 5518027221 5167248999 6170846289 1943649344 9974976477 6877315574 0315918126 2326033491 1691921416 5044177354 6442188572 3770542932 0956099276 8565210594 6390615521 5558598839 6008532874 1803215409 2771427797 4497014681 6323447886 4372272947 5835439916 4230365846 1155729082 8151630140 3544869357 5085022980 5414906958 0123190835 1163042792 3125032560 7109182316 8586253539 9698677788 3567200947 9401594194 8276768573+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• +371499145 9945749054 5480599540 3892267255 7108108552 5908025085 3550322568 5645200317 7619816404 4884520496 0295551239 2580609479 3288654204 0997766392 5221949283 6555667804 1085140909 0510886314 5014362054 3565641245 8499057440 1638437428 7038903331 0055860281 3139288787 1720267659 1048044096 5243630719 6631802091 1211511030 0253983712 7286402056 4185357013 5518027221 5167248999 6170846289 1943649344 9974231178 4113641558 9092871580 2610032366 4848099239 3091589692 7847777288 9611570312 6721929843 8687841255 0698974259 9315154874 3585650284 5532257157 9342908748 2513245291 0695731821 0118515487 2040884130 0818452904 2760181430 8734031861 8509898567 4909870477 5892068501 9451506310 3458352431 6144889999 3030669353 1507323268 3205923987 8948775692 9016444513 4302290822+ε∈(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.