Primality Certificate for (4850^2017-1)/4849

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.179639% 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) = 31.179639%

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 = 7 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₁= 895655 0301918502 4575342135 7440506721 8396188682 9711605071 7017399374 6338366564 4087179156 2596856780 2144692227 9832403364 3978781506 1326308817 9789221762 5704178235 8592177257 0837906720 8972462426 9414406342 0831001614 5611082358 9990514265 0615570317 3583790513 4323833492 1603509646 2586094433 4201287976 9825436974 5995882614 2375924384 3501067218 2782101741 0872210711 3486436749 8515239053 9082181093 9578046504 6359320702 2299164312 8130583264 1043709005 2633356792 6838636562 3362943238 6186635157 2917586107 7018000964 7013001314 1710963676 7127139359 7846185396 1617326815 9489976981 7842689782 5504648971 7712807344 8702663842 3816894621 9939240088 1187910215 8382903437 0324462094 4418779850 9892265134 5439278954 1769244399 8110281195 4842903021 4865299423 2416245721 7619584700 0475417852 2562013385 4564444889 9150578801 8688446443 8215629376 1519957518 5216885095 3263503431 4765514167 9380020614 1566204486 4517292352 9741703059 4892551856 1443875781 5906564304 5462409209 6459438566 9980963745 5041219403 9802043205 0950608037 8910223474 2708316980 7951013711 5347845879 8741563692 6006549118 6451494448 0130414422 5365298260 4046525834 7505290184 6171592014 1432596432 5061107929 8215303453 7406682757 5295575567 1343476838 7023164366 0098473533 6697595492 5715908644 7621360936 6566120071 2274503024 9997188028 2464226632 7247426148 2006287224 7776789467 6988659627 4415567253 4612576558 2486546305 9038224904 4990520611 5657696427 0375647814 4643371535 8126258123 0082144633 5900793335 5834294411 4172000972 4841947709 6204914996 6568898295 9725275514 8146178305 9444257383 7510379480 7722714249 7754724986 8637030597 0356458091 6207495008 6048508386 0227731004 7649946691 7966053267 5580742055 9642833671 4533962532 9251460201 4116143984 5935910374 3883148212 2072165558 0963184648 5846147640 1395929217 5237394620 8139539567 0420203140 8550648763 7827584166 6414266640 4869366769 9660192786 7127248264 3630334703 5071867156 2315927892 6383141701 5070359275 2662555920 8791080395 0381575407 4586183719 9732314031 4033790085 4748794377 4920418644 1239837490 3510843906 6667079920 4737611670 2996834740 1236343302 2753159754 4831302392 2461751162 6248141237 6433186929 5441704306 9917394667 8335635535 1433763319 3592876618 8092968967 8349327769 0394715419 0366990384 3784775391 1963286481 8854750667 3691532131 5854888663 3257886927 8790657370 5430040584 5278091675 0292265873 3305690607 1044565922 1070969128 3037082245 1816758164 7889714203 8974922724 3013682593 5130890658 3039413336 4050943502 0294186504 0924361453
• c₂= 2874038 4255480318 0861097798 8177523767 6181147313 1995097636 1065291583 3001666050 8281428107 6865755817 2699017253 0656297159 2390271881 5871870662 4810875950 3476361524 9791851856 5718863063 1330994356 7110651628 1772050753 5436570811 2213410974 7806634184 4322429399 1756342599 0452287041 9061124587 6226138758 2336754738 1600107895 7004134615 0654863518 3133557528 9992755783 0135804770 2997515038 3097659836 8630508827 7877467231 5061081203 0078195093 0264860795 3935619806 0805403623 3465086187 3428867582 7345015674 7213122317 4203129115 5985003376 6568250506 9114309543 2019078374 1420173185 3115789395 0126340522 9377408385 6310470210 0803606335 8201318258 6780151235 4754877659 7847840659 8832183137 5089189305 0614425412 9615957134 7149463720 7309387868 0505578548 7807228707 6308327990 7311577597 1669115879 6673149439 7676572710 8038456796 9662295682 0530715766 8672471281 0605119805 8601644557 5001512531 7544824771 3186958838 6098093552 1348855211 5492513511 3694177416 6000199675 4171353211 4692912321 4540094204 8045951034 0975230298 1324455415 4792687089 6215413455 4927359742 7672976293 1425021920 4001785245 1511880214 0217803840 3732565318 5568921626 0877534651 4123295981 9524933800 2914750222 2276689028 7123737816 4129010827 3040452658 0686408806 1295302065 1781970169 0411047405 1186183074 8395074149 3505882317 4015572773 1264716062 5409173273 7186271085 5434078445 0448401962 6157095056 5868828409 9457434060 4032988650 2241168754 8899470737 3301626973 1263847456 8040819902 6275275129 4489173053 2282229580 5641828637 9999555666 0363118759 2454731404 5304796626 0313768511 3668578702 3330184518 2342984519 9272624659 4816862129 1133935701 1273482493 3395843075 7602336770 1405356496 1596984282 3282394967 6308623448 3366551672 6697917174 6782605651 8762303006 8110744150 0565616480 3607923931 2037968309 7303832199 6239481038 4029422085 0978058785 8137079419 5202146310 9804462560 0715040806 2989434510 7597183425 4301927656 1248288839 3043053801 3376393413 2555064318 7504374226 3423462820 0335507380 8155287791 3138455456 5225536484 2335532389 1157631468 4556279641 6482040888 4691447837 2932376567 8357300569 5194048646 7948138806 9998163337 1012273319 9152751557 2956416050 9706974876 9662018042 0915716496 8628129326 4288136258 8288904340 6069937898 3321718450 9487906293 6320854848 6211796708 8476276987 5735390776 0777616550 6360823419 1121270920 1380219926 6893715885 0854894252 4349209872 0666332063 6521002160 9588876290 2253479351 1971586228 0412806507 4246438682 1053469068 4875873090 5116479626 6785083836
• c₃= 1 2245972161 6586099705 1711878760 3277856004 6941530078 8309426910 4272822485 0205247627 1469045720 7974019470 7511035398 3941601209 8108793663 6548558207 8984592357 0667429513 1028941483 4885590373 3186863525 0151988981 2335078641 0355526655 9029760469 1065365571 0139747753 9407139249 0607428874 9568618951 5349381439 7681983530 8100258672 7302945741 8017778069 1453712200 5884245444 7710811678 1738697322 5853071835 1842087342 3199861239 6208348371 3916201303 3179937575 1421330854 7927554145 3299998462 6380966436 7071476463
• c₄= 7535990 9939659826 1657127550 6289264313 1173603037 4440796985 4506379511 5522121283 9073161959 7229807940 0333604272 5361900758 7310772191 4345660061 6616919806 1351839893 2446523840 1559051107 6767919059 3614936570 7848613351 9279434001 9827166640 8208988474 5879307998 7259698389 1637031999 1446035940 1069195165 9096325114 9962487668 2509785077 3008056577 3969492859 8809667869 6332779069 6364062463 6343672355 3241756946 0255272304 0484915095 5938294110 2589807717 1064451227 4569965547 0551521675 2529263929 6378158423 2626335482 3677375707 2238842612 4964474280 6747810651 3397764010 8301003893 5466171581 3060976798 6292452594 3115335468 3303508021 7616134388 9106189436 3085365118 0652923003 4653330677 6336260726 1452018154 3784634050 9168964155 3491813663 3535658232 8225372765 5606383173 3239666893 3910663989 4254953612 9815088496 1888524401 4720161680 3767117167 4281334784 7205144579 1924310805 3718114276 3594841738 0048857419 9321053648 8244080696 3421527413 8398554689 1663044894 1729095530 3133613359 5095090230 3544494988 4304127419 8270942521 7040239212 2014574330 0847454982 3059485231 9723476948 1208275236 7616509119 7592507228 5177022696 7452963268 2032716159 7140558436 0371445803 4896713382 0505869730 2356313888 9686461302 8172931615 8963484665 9057320021 5413353559 1719779658 5656305993 5117149439 8289415699 5216360653 6587397638 7504513960 7255026094 2126813959 0969239721 3874332785 6001125100 5335864727 7896121265 2575991280 7879780637 3248232171 1287946056 7936417589 7574694899 7604275081 6451634413 1754199860 7907759315 4265455794 0550428446 2817609630 7480474783 1202324799 2269866599 6693409818 7778711260 3085246860 2824083663 2136784123 2652367265 4774012964 9454754982 1202144074 1329418831 7706317011 5871623859 4641063951 5484324313 8635038917 4441938937 0381513387 5391544757 1109308341 3394419063 5483272285 6913300173 9858537119 8115801646 0783484887 5997199287 9838783919 2864535404 2671617530 5756073576 0098604013 8579637217 6532580497 9295586456 2717268828 0627798168 4399065674 5458841228 5578856614 2055479771 4718057477 7220448964 1240112591 9738092395 7595243623 8353206167 0757397233 6719384175 8513652543 0958541447 2058304842 1961645314 1506768152 5336535799 6270444743 9521336671 5689964278 2243982244 4110037098 7966816793 2840835626 2783384374 7130432954 1588025494 6329895559 4147433612 1572433194 2872826841 2003722513 9120385255 1076939771 1069450626 5893060066 9571435232 4325750169 5871792997 9331340439 6524399771 9138517285 9772869235 2966211459 0313383262 7545481402 0244193529 4037822306 4968427180 4011047725 9424755197 3011537445 3556628067 8168041271 5749542818 5932159147 6262309429 8786263418 4445405478 8553669898 9293780589 8210225726 4898391558 2597500955 6664675057 0051256357 6758818941 2880181052 3146819028 5669264669 8544302223 1083718796 0513308476 7028075644 5479185176 8593459882 7352670388 1645102902 8580801089 3750558203 1500455099 7214397466 0077354000 8793523305 9258833763 0194609006 7441322575 0742568745 2753372988 0380579185 3205503501 4721631198 7611336847 6983746234 5110220686

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

Continued Fraction

We approximate c₁/F by a continued fraction u/v such that v is maximal while remaining less than F² / N^1/2 = 224169703 5814775443 7198102487 2985425007 5612323125 0508262096 7516807405 1919287688 5443635260 8378198316 2814127268 2836740630 8187484995 7740653065 5097118374 3399566542 3898774229 2241154062 1136094110 0630236905 3813936424 6986665345 3910135368 3398228996 2562374213 5915568631 8241429176 3477930184 3076950246 5786154425 3387885262 8716590692 9413386501 3143208091 4621594855 0726139317 4379613951 8405021436 8665572705 3782188956 8291146670 6680638597 7629540102 2549844306 3372058140 6053767637 1405065946 1117974533 0491969482 7117482761 7659390562 8528964348 2735210050 6181682254 1860039189 7552308729 3253999404 0149622594 9171536988 5699282527 0104745268 4133496583 7888020728 0781597527 2857736475 4990854974 5801817215 1341444669 4359162900 6507640955 2327754818 8504952989 8046716585 7382921130 0551167736 6595348837 8845814293 3788252060 6014350945 0274459863 3834830216 8139410865 2096024664 4864160989 3632589146 9021010499 2670865512 9575864585 5105366356 4776938284 8889110998 2821228621.

With those constraints, the unique continued fraction is: {0, 6, 1, 6, 1, 2, 1, 4, 1, 15, 1, 1, 1, 4, 2, 1, 2, 6, 5, 6, 4, 1, 9, 39, 1, 1, 6, 11, 8, 2, 1, 1, 7, 2, 1, 7, 2, 1, 1, 44, 1, 1, 5, 2, 73, 1, 13, 2, 1, 3, 3, 20, 1, 1, 2, 7, 3, 1, 1, 1, 1, 1, 86, 2, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 8, 4, 3, 3, 2, 3, 6, 2, 3, 1, 13, 1, 16, 3, 7, 1, 3, 7, 1, 3, 1, 12, 8, 1, 1, 1, 1, 1, 1, 23, 1, 7, 1, 3, 1, 3, 7, 1, 1, 2, 2, 41, 2, 2, 3, 1, 29, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 1, 2, 261, 2, 1, 14, 9, 2, 3, 1, 5, 5, 5, 2, 5, 2, 2, 11, 3, 2, 3, 1, 2, 1, 2, 1, 1, 3, 9, 2, 1, 2, 1, 1, 1, 2, 4, 1, 14, 2, 3, 4, 1, 3, 8, 1, 8, 1, 2, 1, 2, 1, 1, 7, 4, 1, 6, 1, 7, 3, 1, 1, 2, 2, 2, 1, 1, 6, 1, 4, 2, 1, 10, 1, 1, 1, 8, 5, 4, 2, 43, 18, 1, 3, 2, 1, 3, 1, 3, 6, 8, 1, 42, 1, 4, 2, 1, 2, 2, 1, 2, 2, 4, 3, 1, 2, 2, 5, 13, 8, 1, 20, 1, 2, 1, 1, 15, 1, 2, 2, 1, 7, 19, 166, 1, 138, 1, 1, 1, 1, 4, 7, 1, 3, 1, 5, 75, 2, 1, 4, 1, 4, 1, 3, 5, 2, 1, 80, 2, 1, 2, 2, 2, 3, 1, 3, 1, 6, 2, 2, 2, 2, 3, 2, 4, 12, 1, 43, 1, 5, 1, 1, 5, 1, 7, 1, 2, 4, 8, 2, 2, 1, 1, 1, 10, 8, 1, 19, 1, 14, 1, 1, 1, 2, 1, 102, 5, 5, 3, 13, 4, 1, 2, 75, 2, 14, 1, 1, 1, 6, 2, 1, 30, 1, 6, 1, 1, 1, 1, 2, 1, 1, 1, 14, 3, 9, 1, 2, 1, 3, 2, 3, 7, 1, 1, 1, 7, 1, 1, 5, 2, 15, 12, 2, 2, 1, 31, 189, 2, 12, 2, 1, 4, 1, 7, 1, 1, 1, 20, 3, 2, 31, 2, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 1, 7, 3, 3, 1, 5, 7, 2, 1, 3, 2, 2, 1, 32, 2, 1, 1, 5, 1, 5, 1, 5, 1, 4, 1, 1, 9, 2, 93, 2, 1, 1, 1, 1, 1, 1, 6, 5, 2, 2, 6, 43, 1, 2, 15, 1, 1, 1, 6, 4, 1, 157, 1, 6, 1, 1, 1, 1, 2, 3, 1, 6, 1, 1, 1, 1, 6, 3, 1, 1, 6, 137, 1, 1, 2, 1, 1, 16, 1, 1, 1, 3, 6, 2, 5, 1, 1, 7, 1, 1, 17, 22, 2, 44, 2, 1, 1, 1, 2, 6, 4, 1, 5, 1, 23, 1, 6, 1, 13, 2, 1, 1, 2, 2, 1, 4, 1, 1, 7, 2, 3, 1, 1, 3, 5, 4, 1, 19, 1, 1, 7, 4, 1, 1, 38, 1, 28, 2, 1, 1, 7, 1, 1, 6, 3, 11, 2, 1, 2, 1, 4, 1, 2, 8, 1, 1, 3, 2, 3, 2, 1, 1, 3, 1, 3, 1, 12, 4, 30, 1, 1, 3, 1, 21, 3, 7, 3, 59, 23, 56, 1, 2, 16, 9, 2, 9, 97, 1, 1, 1, 20, 1, 1, 2, 16, 1, 3, 1, 3, 55, 1, 126, 3, 1, 1, 1, 389, 11, 1, 9, 1, 2, 1, 3, 1, 2, 1, 7, 1, 1, 1, 5, 1, 1, 13, 5, 2, 1, 1, 58, 2, 1, 1, 1, 9, 1, 1, 22, 1, 3, 1, 1, 7, 2, 2, 1, 1, 20, 1, 2, 17, 2, 3, 7, 1, 1, 14, 4, 12, 9, 5, 1, 37, 3, 8, 1, 1, 4, 6, 1, 1, 2, 1, 1, 16, 1, 8, 3, 3, 5, 1, 3, 1, 1, 1, 2, 1, 7, 3, 2, 18, 2, 1, 1, 3, 1, 116, 1, 4, 1, 1, 1, 1, 16, 1, 5, 1, 6, 1, 2, 2, 3, 1, 2, 1, 1, 1, 13, 1, 3, 1, 1, 7, 1, 2, 1, 3, 3, 4, 2, 1, 3, 3, 1, 23, 1, 1, 8, 8, 1, 1, 17, 4, 4, 1, 2, 1, 1, 2, 13, 6, 12, 1, 2, 2, 1, 6, 3, 1, 5, 3, 1, 4, 2, 1, 1, 1, 2, 1, 12, 2, 4, 6, 4, 2, 1, 1, 1, 1, 5, 4, 4, 2, 1, 1, 1, 12, 1, 2, 1, 2, 10, 1, 1, 13, 1, 1, 2, 1, 1, 1, 1, 5, 4, 4, 1, 2, 4, 5, 1, 6, 1, 1, 1, 3, 12, 2, 4, 1, 1, 4, 8, 5, 1, 1, 16, 10, 1, 4, 7, 1, 1, 2, 3, 3, 2, 1, 3, 1, 20, 1, 17, 1, 2, 1, 9, 13, 1, 9, 3, 4, 2, 16, 1, 41, 1, 4, 1, 8, 4, 1, 3, 1, 4, 27, 1, 2, 2, 4, 29, 2, 2, 1, 1, 4, 2, 1, 3, 2, 2, 8, 5, 5, 6, 1, 1, 4, 1, 125, 2, 1, 12, 1, 3, 1, 6, 1, 2, 1, 3, 1, 1, 1, 2, 5, 6, 11, 1, 6, 3, 1, 26, 1, 1, 1, 3, 18, 1, 1, 4, 3, 1, 3, 6, 1, 1, 1, 1, 317, 5, 6, 3, 2, 1, 5, 56, 5794, 10, 2, 2, 5, 1, 14, 2, 1, 1, 20, 2, 1, 5, 6, 1, 130, 1, 1, 2, 3, 2, 1, 1, 2, 7, 2, 1, 2, 4, 1, 1, 1, 1, 1, 2, 19, 1, 1, 1, 1, 22, 1, 1, 1, 2, 172, 2, 4, 2, 3, 4, 6, 2, 1, 2, 1, 2, 3, 2, 2, 5, 1, 1, 1, 3, 9, 2, 7, 1, 3, 2, 7, 1, 30, 2, 4, 1, 28, 1, 3, 11, 1, 1, 4, 1, 24, 2, 5, 1, 2, 1, 1, 3, 1, 1, 1, 2, 1, 929, 12, 1, 20, 1, 16, 13, 6, 53, 1, 1, 2, 4, 1, 41, 1, 3, 2, 1, 14, 4, 2, 2, 51, 10, 1, 2, 2, 12, 2, 4, 3, 7, 4, 1, 1, 1, 4, 1, 4, 1, 2, 2, 1, 2, 1, 1, 2, 1, 3562, 1, 1, 26, 3, 6, 2, 3, 9, 1, 1, 1, 30, 1, 25, 1, 1, 1, 1, 1, 1, 3, 1, 4, 1, 6, 2, 1, 3, 3, 1, 1, 4, 1, 18, 1, 1, 1, 2, 3, 1, 3, 8, 1, 2, 3, 2, 1, 15, 1, 7, 49, 6, 1, 1, 4, 1, 25, 4, 1, 5, 1, 30, 1, 1, 4, 11, 2, 6, 2, 1, 23, 11, 1, 4, 4, 1, 2, 2, 1, 17, 1, 1, 2, 1, 2, 4, 1, 4, 5, 5, 1, 3, 6, 1, 33, 1, 14, 2, 3, 1, 22, 3, 1, 3, 2, 1, 2, 2, 2, 3, 1, 2, 2, 1, 2, 1, 1, 1, 3, 3, 1, 6, 3, 1, 1, 6, 2, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 5, 6, 1, 21, 1, 59, 1, 4, 2, 4, 1, 7, 2, 1, 28, 1, 3, 1, 4, 1, 3, 2, 1, 5, 6, 2, 8, 3, 6, 2, 1, 6, 2, 3, 1, 21, 1, 1, 35, 1, 1, 3, 1, 2, 4, 1, 10, 1, 8, 2, 4, 1, 1, 1, 2, 1, 5, 3, 1, 1, 1, 10, 1, 14, 2, 1, 1, 1, 2, 1, 2, 3, 5, 1, 11, 1, 1, 7, 3, 5, 9, 1, 4, 1, 5, 1, 3, 2, 1, 2, 10, 12, 1, 63, 3, 3, 1, 3, 43, 1, 2, 1, 1, 1, 16, 2, 1, 3, 49, 48, 1, 1, 1, 1, 4, 6, 2, 2, 1, 1, 7, 47, 1, 1, 1, 7, 4, 1, 18, 1, 5, 5, 3, 1, 1, 1, 2, 6, 1, 72, 10, 1, 6, 16, 5, 25, 2, 3, 8, 1, 1, 3, 1, 1, 3, 10, 22, 2, 4, 1, 2, 4, 1, 12, 2, 1, 1, 30, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 43, 2, 2, 1, 5, 1, 40, 2, 7, 5, 1, 1, 3, 1, 1, 1, 3, 1, 4, 1, 1, 10, 4, 7, 6, 1, 10, 2, 1, 2, 1, 2, 4, 12, 18, 1, 3, 1, 2, 5, 8, 2, 1, 1, 4, 1, 5, 2, 1, 4, 2, 6, 1, 4, 4, 6, 1, 3, 18, 3, 2, 2, 1, 8, 2, 1, 2, 1, 3, 1, 4, 4, 3, 1, 3, 1, 2, 6, 8, 3, 4, 32, 1, 1, 2, 1, 8, 1, 2, 1, 2, 2, 1, 1, 23, 33, 2, 5, 1, 1, 17, 2, 1, 1, 56, 1, 10, 5, 3, 3, 2, 5, 1, 4, 2, 20, 2, 2, 3, 5, 1, 1, 1, 13, 4, 3, 1, 15, 3, 1, 43, 2, 6, 6, 6, 3, 2, 18, 5, 1, 5, 1, 5, 1, 6, 1, 1, 14, 4, 2, 1, 2, 3, 1, 1, 3, 2, 34, 1, 5, 3, 2, 19, 1, 3, 2, 1, 1, 5, 1, 2, 8, 2, 1, 32, 3, 1, 4, 2, 2, 1, 1, 25, 1, 2, 4, 3, 1, 1, 1, 5, 20, 3, 2, 4, 1, 1, 2, 9, 3, 1, 3, 2, 1, 2, 1, 1, 1, 1, 3, 1, 10, 1, 2, 1, 2, 1, 1, 1, 8, 1, 1, 2, 2, 3, 1, 2, 1, 7, 1, 3, 1, 3, 1, 2, 3, 7, 1, 7, 1, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 3, 1, 4, 1, 4, 1, 2, 2, 5, 3, 1, 1, 2, 2, 3, 2, 1, 1, 72, 3, 1, 2, 61, 1, 2, 2, 1, 1, 1, 2, 8, 1, 1, 12, 1, 2, 1, 1, 4, 1, 1, 1, 2, 3, 4, 1, 18, 1, 9, 3, 5, 8, 508, 1, 1, 2, 1, 4, 1, 1, 2, 2, 2, 2, 1, 9, 1, 39, 1, 3, 1, 2, 10, 7, 1, 2, 1, 1, 3, 33, 2, 26, 1, 2, 1, 1, 2, 1, 29, 1, 1, 4, 1, 1, 6, 7, 1, 71, 2, 8, 1, 2, 13, 1, 59, 15, 1, 1, 1, 2, 1, 7, 1, 1, 2, 5, 4, 13, 2, 1, 1, 1, 1, 4, 3, 2, 15, 2, 2, 1, 1, 13, 2, 1, 17, 5, 1, 16, 2, 1, 20, 1, 3, 8, 3, 1, 1, 2, 9, 1, 8, 1, 6, 24, 20, 7, 1, 2, 3, 1, 2, 1, 1, 1, 3, 6, 1, 47, 1, 3, 1, 2, 13, 39, 1, 1, 10, 1}, giving these values for u and v:

• u= 19133678 4332413072 3280305686 6732262167 3947380459 5296261273 6522465796 7322192407 1676058191 5931782841 7427327907 7032142558 2040808828 3647339136 1677023494 4708550812 4555802972 2572103220 4744051633 0118714990 9984323119 0046514501 5120325562 8022911567 8019604469 9029355857 9531735540 8582411194 7687815215 1695254021 5865911541 9489373809 7449634715 9890431693 7575989431 3977534841 1343380389 1405263581 7434417349 8341170618 6833587227 0652617690 4227743382 9398932350 7467807413 5071866942 1902713933 9271432775 2957959214 4041828721 3435442563 7599798399 9439371847 0348425931 4070829994 5124783060 3323031938 8166953478 6617462920 6987410490 4758204108 5663553899 3631668218 2463227638 3274603772 6362067525 3558596652 0299342475 4069829580 2781796596 8611159715 6684880815 5194020688 8227254297 8053570060 6258011094 9878889330 0996083208 2008262716 3100291170 9407374223 1759489068 7210015872 8853515876 8437001416 1113482160 6879790043 9649484654 9448644094 6686466069 7563337110 2443754957
• v= 131463383 1318456336 0179828292 8738850873 3916762236 9018846672 7550875088 4935978727 8434398002 9084004601 1018996274 2114434227 2805759477 8609543713 6795895373 4669446287 1900682180 5928400258 0476102768 5125657383 6997876857 9357416939 3230853132 8077654395 0295233717 8201136575 5658243123 4381356834 6541274333 8306025927 8223169810 1551248805 7657574884 6718041306 4889092619 9088707645 3694420302 9675315862 4857326843 8524508446 9071509372 4903807712 2207671932 3408045325 6843627911 0791068851 2801869189 7337700142 7076979732 5842412854 0747452971 5723840974 3226877245 3409267088 4004991821 1265967049 6744899870 7105005350 6945068673 4508707017 4954064238 0937549227 9437552995 3520529255 5445115972 1450331755 4457905349 8860507742 0198455682 9177406210 9396912745 5443682437 8903059003 7723020283 6157364863 6863845428 2941856475 3170336078 0416925802 4617089015 1117175056 4041631533 4485602770 7070505079 3498885616 9665644773 5053413437 6609321168 5781096127 8673149377 2564940320 8777206228

… as taking one more term in the continued fraction would give a value of v of 645891593 2452146053 4586773436 8481136638 8613546314 3208003214 9917141671 4375888654 6147140194 8766787169 7917190311 5219651452 1259636672 5138335828 8191809422 2298037797 9633623507 5241770120 0109522201 7446262036 7641470966 0831994954 8140051529 3940495954 4415376180 8656990658 0834903551 3937578454 4875478168 8870752049 3772950251 1109261368 6694345897 4114204795 1398350358 0648061316 6437567894 3093176681 4101273849 4282376726 2492654958 9418550038 9034103277 9740664131 4667497313 4562699159 9952746937 6904284309 2166365203 2297958413 1853161906 7711094300 5294795164 8544441468 2348317497 8479088390 1400874191 7147482546 2846590714 2562098337 4660195857 5006276140 0128382778 6077454297 0993790743 6406214168 0215106310 6371535144 0734607061 1038304540 2069014285 2689031315 4528608630 9458605726 0221690248 6623341120 6059380919 3028513475 3841998375 6294089453 6760982296 9973574043 5439203513 2202899078 0567575208 0520037181 8965217248 2652547590 2128069263 0891578403 3411646632 4551603575, which is too large.

We also need to calculate d = floor(c₄·v/F + 0.5) = 160989693 0110041716 5255734763 7341409673 8745086880 3961310201 4883388576 1913411833 0797291685 4196906222 1249050125 5422721165 8138827422 9824179774 8351111147 3072387902 9589022733 7205502276 2651134685 3259392047 0226740639 3582623036 1280146308 2822570668 9327587369 9326156936 1391611919 7773663528 9075402391 5617834534 0075400057 7530389255 8149084091 3075154829 1395530380 5678518873 3366694821 9666860314 8224036061 5400660150 1754609825 8018661534 4123914182 2422673688 7413669935 7327359276 8306587029 8696122010 8767218701 4783923464 9685987634 7231055259 5181769039 6372948028 9407471231 0545494496 5845677563 2773318986 9945718818 6906707520 3194774508 1641847934 1362540710 9224142529 6295833772 6527260622 6465448171 6927311118 8224270037 2458277233 7163230704 4696740831 6838381975 5049577299 6249783050 0368615421 8561292096 2787765416 8985908428 4425331402 2524332178 1552407223 0345540544 3960391764 7105976965 7512313319 6201714779 6927316412 0361428454 9394317518 8731579975 0857369105 2571510444 9815322850 4342278188 5441373844 7081238294 6282405739 2243391722 3005443944 0025561573 3035147794 8674106279 3831085973 2992242699 5037707051 9511447805 0142738384 6630809006 3202025984 2773182605 1724531151 2716428892 1729501435 9783901506 9352086948 4325805409 6779750404 4982303305 4581618496 0995199044 2566006499 2416870815 2819318797 1912998403 8394915085 3381013674 3601238150 4163116090 3873980923 6394253776 4753042624 2365039618 0301700064 6510759991 6026933017 1497982622 0705223174 1232164249 3567346414

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₁= +131463383 1318456336 0179828292 8738850873 3916762236 9018846672 7550875088 4935978727 8434398002 9084004601 1018996274 2114434227 2805759477 8609543713 6795895373 4669446287 1900682180 5928400258 0476102768 5125657383 6997876857 9357416939 3230853132 8077654395 0295233717 8201136575 5658243123 4381356834 6541274333 8306025927 8223169810 1551248805 7657574884 6718041306 4889092619 9088707645 3694420302 9675315862 4857326843 8524508446 9071509372 4903807712 2207671932 3408045325 6843627911 0791068851 2801869189 7337700142 7076979732 5842412854 0747452971 5723840974 3226877245 3409267088 4004991821 1265967049 6744899870 7105005350 6945068673 4508707017 4954064238 0937549227 9437552995 3520529255 5445115972 1450331755 4457905349 8860507742 0198455682 9177406210 9396912745 5443682437 8903059003 7723020283 6157364863 6863845428 2941856475 3170336078 0416925802 4617089015 1117175056 4041631533 4485602770 7070505079 3498885616 9665644773 5053413437 6609321168 5781096127 8673149377 2564940320 8777206228
• z₂= -87306037 2023052055 5694310507 9783537144 0055896876 4551174581 0168201275 9745190108 9876914084 3912829256 4963107925 4199361555 7069637308 6876240009 3184672388 3015234757 7003782472 4944277812 3730443333 3413971872 1222535231 0799760394 6491536868 9065876041 2851072219 8719686649 8321411206 2981098376 2123922485 2293808548 1908537480 1474352249 5570255949 1837582192 9357802088 1652425122 5080571187 6721060191 5139512762 1577305453 7234977277 8495816471 3986489500 1081617806 3625873736 5736996646 7757629238 3703779171 3705379899 1302027357 6891436886 2756084259 6761552662 2399604401 7812224550 9636369961 4465089279 0467871649 7322478249 0381191155 5491995339 8665347250 9731055188 3054716895 3437375797 6219913851 3143936311 7363626725 9207399088 6955145251 0902683673 1909482131 3704317664 1276546645 2896647732 6854369212 4191170897 7303495894 2410096963 5804898660 3551478786 2406939641 5318046452 0800713018 5292759950 1885558790 0009533435 7619953064 7287246172 0188159373 7004139500 6494099264 5859931315 6000681901 1012276386 6642984219 2786629698 1714751280 4174020107 8530107418 2658338311 6423973363 4036024410 1169437179 2723615982 1601998274 9569332146 3856159688 8805498930 2574025570 1504452674 9078652700 4688854746 0846949536 3088585533 7342575541 5773974324 0652426126 5279936825 9810585232 3283367808 0549185597 1004825513 5019315356 5353993856 7213606434 8212797843 8430703538 2843268339 6411735472 1821244357 3152564774 5905654396 2608285334 0697671642 8902126337 6553976124 0973137933 6475133850 1355037134
• z₃= +2840237 6981663075 8010286630 9841763601 7570110097 0984945780 7421531123 5783094143 8626852917 0301661287 5284818300 5643080240 5132981232 5548896516 8132984865 3793671188 5162873425 3252946504 0058869041 4655320675 8183951459 4457988672 3730373059 5319739833 5979772412 8379941973 1651062081 5686571851 2521628818 3113465150 0657050536 5372349184 7596118971 5046716746 7478418761 7966138916 9613645478 5853029018 9894206968 7939578326 2372914631 1614881120 7795402782 6859107531 9513802295 8393063670 7310069495 8224900881 7222595984 8422199227 4398862520 3253825746 2019707067 9483534669 2376964517 8475580262 6265190087 2423671590 6408324592 7502210093 1422514467 6988385857 8409014129 9759213847 3171470657 3918987250 9856036458 7764914278 1279501638 3727964382 4292230280 1477851652 1281585699 3096560303 4677804641 2730589740 7270114712 1612522966 8979042496 2503937707 8261245101 8535993418 7340962062 1374456987 1501102023 1029746751 3223458245 4043100318 7730227863 8080671087 5042799845 2245826592 5606487072 4437859508 8405671522 1536485210 5834136081 3391580291 3706781570 4815721766 8052571515 9928956894 1245188204 4435236335 7226665207 5736839219 9173173254 7375898947 8146644468 3560625289 6844090362 1229496637 0315086930 6538469569 5047910713 9592924338 4561393071 8840663669 5359125522 0367360945 4988265340 4782415811 5615357427 4963748409 3089614748 2200960886 8560517265 7645560210 8858293014 5088111861 4147077512 0344614053 8708080579 0328226424 4777976499 1270692568 1832734970 9121143647 7494915667 2576855601 6526646149 8852895863 8247303070 5129785515 9902324443 8795457270 3381128217 8043537459 6017210131 8326131287 3444283881 0088449798 9547929483 2552689733 6448356023 4053884373 1492843935 6492368298 8349880382 6651059831 6562087522 6428706814 6495961907 3381390222 1583318385 6835063964 7425859297 0408133257 6936547798 7971958692 1762882175 7900081570 7836082998 8113072505 0003021492 2259608463 7351809638 6908167145 2087305713 8371165637 7847601326 3486327192 1252399173 3463313631 5607835923 9702070133 4207768834 5384208509 7060294336 6738893050 8774176930 4725029340 1071052662 1660854994 8522739222 5094394974 5048464680 7088881893 8853616239 7175426240 6780115173 8850253501 6561715017 5289137604 8145011077 3551100053 8974410879 9655896874 8649037461 8431065444 6272231207 9303837549 7567041988 2878593862 4543279090 9873621215 5550930236 9457080347 9172031340 2230911258 8550327104 7163289185 8553473187 8024007200 0668019975 1025953869 3932036572 5829933451 8876041594 8685595798 1852102846 5289828065
• z₄= -160989693 0110041716 5255734763 7341409673 8745086880 3961310201 4883388576 1913411833 0797291685 4196906222 1249050125 5422721165 8138827422 9824179774 8351111147 3072387902 9589022733 7205502276 2651134685 3259392047 0226740639 3582623036 1280146308 2822570668 9327587369 9326156936 1391611919 7773663528 9075402391 5617834534 0075400057 7530389255 8149084091 3075154829 1395530380 5678518873 3366694821 9666860314 8224036061 5400660150 1754609825 8018661534 4123914182 2422673688 7413669935 7327359276 8306587029 8696122010 8767218701 4783923464 9685987634 7231055259 5181769039 6372948028 9407471231 0545494496 5845677563 2773318986 9945718818 6906707520 3194774508 1641847934 1362540710 9224142529 6295833772 6527260622 6465448171 6927311118 8224270037 2458277233 7163230704 4696740831 6838381975 5049577299 6249783050 0368615421 8561292096 2787765416 8985908428 4425331402 2524332178 1552407223 0345540544 3960391764 7105976965 7512313319 6201714779 6927316412 0361428454 9394317518 8731579975 0857369105 2571510444 9815322850 4342278188 5441373844 7081238294 6282405739 2243391722 3005443944 0025561573 3035147794 8674106279 3831085973 2992242699 5037707051 9511447805 0142738384 6630809006 3202025984 2773182605 1724531151 2716428892 1729501435 9783901506 9352086948 4325805409 6779750404 4982303305 4581618496 0995199044 2566006499 2416870815 2819318797 1912998403 8394915085 3381013674 3601238150 4163116090 3873980923 6394253776 4753042624 2365039618 0301700064 6510759991 6026933017 1497982622 0705223174 1232164249 3567346414

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.

As z₁ is > 0 and z₄ is < 0, we know that P has at least one real root r₁ > 0. This is easily found:

• r₁= 0+ε∈(0,1)

Note that the root is not an integer but actually lies in the interval (r₁,r₁+1).

To see if P has any more real roots, we examine the quadratic derivative P' of P = 3·z₁·x² + 2·z₂·x + z₃, which we express in the usual quadratic form as a·x² + b·x + c

• a= +394390149 3955369008 0539484878 6216552620 1750286710 7056540018 2652625265 4807936183 5303194008 7252013803 3056988822 6343302681 8417278433 5828631141 0387686120 4008338861 5702046541 7785200774 1428308305 5376972151 0993630573 8072250817 9692559398 4232963185 0885701153 4603409726 6974729370 3144070503 9623823001 4918077783 4669509430 4653746417 2972724654 0154123919 4667277859 7266122936 1083260908 9025947587 4571980531 5573525340 7214528117 4711423136 6623015797 0224135977 0530883733 2373206553 8405607569 2013100428 1230939197 7527238562 2242358914 7171522922 9680631736 0227801265 2014975463 3797901149 0234699612 1315016052 0835206020 3526121052 4862192714 2812647683 8312658986 0561587766 6335347916 4350995266 3373716049 6581523226 0595367048 7532218632 8190738236 6331047313 6709177011 3169060850 8472094591 0591536284 8825569425 9511008234 1250777407 3851267045 3351525169 2124894600 3456808312 1211515238 0496656850 8996934320 5160240312 9827963505 7343288383 6019448131 7694820962 6331618684
• b= -174612074 4046104111 1388621015 9567074288 0111793752 9102349162 0336402551 9490380217 9753828168 7825658512 9926215850 8398723111 4139274617 3752480018 6369344776 6030469515 4007564944 9888555624 7460886666 6827943744 2445070462 1599520789 2983073737 8131752082 5702144439 7439373299 6642822412 5962196752 4247844970 4587617096 3817074960 2948704499 1140511898 3675164385 8715604176 3304850245 0161142375 3442120383 0279025524 3154610907 4469954555 6991632942 7972979000 2163235612 7251747473 1473993293 5515258476 7407558342 7410759798 2604054715 3782873772 5512168519 3523105324 4799208803 5624449101 9272739922 8930178558 0935743299 4644956498 0762382311 0983990679 7330694501 9462110376 6109433790 6874751595 2439827702 6287872623 4727253451 8414798177 3910290502 1805367346 3818964262 7408635328 2553093290 5793295465 3708738424 8382341795 4606991788 4820193927 1609797320 7102957572 4813879283 0636092904 1601426037 0585519900 3771117580 0019066871 5239906129 4574492344 0376318747 4008279001 2988198529 1719862631 2001363802 2024552773 3285968438 5573259396 3429502560 8348040215 7060214836 5316676623 2847946726 8072048820 2338874358 5447231964 3203996549 9138664292 7712319377 7610997860 5148051140 3008905349 8157305400 9377709492 1693899072 6177171067 4685151083 1547948648 1304852253 0559873651 9621170464 6566735616 1098371194 2009651027 0038630713 0707987713 4427212869 6425595687 6861407076 5686536679 2823470944 3642488714 6305129549 1811308792 5216570668 1395343285 7804252675 3107952248 1946275867 2950267700 2710074268
• c= +2840237 6981663075 8010286630 9841763601 7570110097 0984945780 7421531123 5783094143 8626852917 0301661287 5284818300 5643080240 5132981232 5548896516 8132984865 3793671188 5162873425 3252946504 0058869041 4655320675 8183951459 4457988672 3730373059 5319739833 5979772412 8379941973 1651062081 5686571851 2521628818 3113465150 0657050536 5372349184 7596118971 5046716746 7478418761 7966138916 9613645478 5853029018 9894206968 7939578326 2372914631 1614881120 7795402782 6859107531 9513802295 8393063670 7310069495 8224900881 7222595984 8422199227 4398862520 3253825746 2019707067 9483534669 2376964517 8475580262 6265190087 2423671590 6408324592 7502210093 1422514467 6988385857 8409014129 9759213847 3171470657 3918987250 9856036458 7764914278 1279501638 3727964382 4292230280 1477851652 1281585699 3096560303 4677804641 2730589740 7270114712 1612522966 8979042496 2503937707 8261245101 8535993418 7340962062 1374456987 1501102023 1029746751 3223458245 4043100318 7730227863 8080671087 5042799845 2245826592 5606487072 4437859508 8405671522 1536485210 5834136081 3391580291 3706781570 4815721766 8052571515 9928956894 1245188204 4435236335 7226665207 5736839219 9173173254 7375898947 8146644468 3560625289 6844090362 1229496637 0315086930 6538469569 5047910713 9592924338 4561393071 8840663669 5359125522 0367360945 4988265340 4782415811 5615357427 4963748409 3089614748 2200960886 8560517265 7645560210 8858293014 5088111861 4147077512 0344614053 8708080579 0328226424 4777976499 1270692568 1832734970 9121143647 7494915667 2576855601 6526646149 8852895863 8247303070 5129785515 9902324443 8795457270 3381128217 8043537459 6017210131 8326131287 3444283881 0088449798 9547929483 2552689733 6448356023 4053884373 1492843935 6492368298 8349880382 6651059831 6562087522 6428706814 6495961907 3381390222 1583318385 6835063964 7425859297 0408133257 6936547798 7971958692 1762882175 7900081570 7836082998 8113072505 0003021492 2259608463 7351809638 6908167145 2087305713 8371165637 7847601326 3486327192 1252399173 3463313631 5607835923 9702070133 4207768834 5384208509 7060294336 6738893050 8774176930 4725029340 1071052662 1660854994 8522739222 5094394974 5048464680 7088881893 8853616239 7175426240 6780115173 8850253501 6561715017 5289137604 8145011077 3551100053 8974410879 9655896874 8649037461 8431065444 6272231207 9303837549 7567041988 2878593862 4543279090 9873621215 5550930236 9457080347 9172031340 2230911258 8550327104 7163289185 8553473187 8024007200 0668019975 1025953869 3932036572 5829933451 8876041594 8685595798 1852102846 5289828065

As b²-4·a·c is negative, P' has no real roots. Therefore, P has no turning points and is monotonic, implying that r₁ is the only real root of P.

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