Primality Certificate for (9751^2161-1)/9750

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

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

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

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

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 = 71 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₁= 1350379758 8340148080 2943506565 6894281779 7592339998 3985676090 5246102311 1204881417 7018923191 1475865655 1149240233 9088432690 3381376167 8592149080 8713181283 5390866491 1807138035 1606668260 8337297323 3758780947 8501650369 8370809681 3449947422 2509379714 7839878033 3439531052 6066733727 3652099789 1188825401 9963917270 5724461825 2881486557 4830732008 9938530640 2029600419 5389250682 7153845009 8159854937 1100318624 0586478419 5524759070 3296085258 6509848081 7659449433 6869760585 3841818840 1072268616 0770330633 2827276635 7704137017 6482326443 9422871234 3854779814 0668184849 6293053361 4949310847 6249777543 6875602811 7830735347 8839572493 0754863297 5203313328 8148391026 2880973474 3118771069 1286728193 0435939546 6460415586 1327640760 7474846221 2773686603 4028866525 1654405709 3293950814 4446177446 0287044117 7907363774 8439742559 6638597676 8562898895 4172923354 1549097429 0383209383 5946212446 4648363155 5208045853 4716116850 3293237677 9619033762 5999528140 4535531641 8112198620 3930978148 1496133630 6384275307 9110164542 9765868367 9008575772 3248053982 9695935538 6807356726 2471010846 7410534544 2826909099 1051195000 1488710712 0487464435 8126018148 3328862783 0355474297 9924174471 0228041316 5811361138 9128050185 1187154884 1632988282 8840844601 4559729331 0843165702 9666381302 7570788662 7365704748 9563947451 0389345613 7350153432 4435703389 9537506619 7744700515 7043783945 8881774539 9841871487 1445050290 5074178191 0281557029 4178785384 2827719423 4475777684 7804638368 7327360989 2689289650 3665534541 0091976648 6760359469 8517041598 7626011026 4297343544 8894149045 8633077038 4064844554 3499246717 0512314946 4952292819 5041440750 7380069899 2525668684 7000553219 1657140028 7419097655 1781511489 2560383346 7844888499 4747356191 8987036993 6028522405 4348062328 1436524078 6324725000 1104575732 3858434476 2159318358 0117353930 0324931752 6759269301 3184193548 3951349836 3314427076 0161427828 7399436121 6680903939 1370871640 0045846224 5612205222 5161315283 9720207698 2969433429 1915782142 0486930512 6911545457 1778424133 4374210345 9882908352 6759577181 9230773495 2664909549 2723058187 5630134298 9121391858 2055202927 2644814934 7376092359 9834864910 2145416007 4987816400 8861614904 8303201557 8205828473 5459736675 1272490910 4876340251 0647047990 6355518741 6684345036 0645850408 6763312941 7145653850 1409189505 3475816585 5408543340 1984267276 6822299403 9221182449 7964428604 4801679454 9304514033 0078965751 9265357092 3948948083 9544846689 9327654872 4081717646 1337946336 7445774042 8951740401 2648459221 1366171212 2982821846 5896311438 9068750725 7877610555 7989776870 3204998921 1609287554 8123331220 3581260828 6146657726 1645852317 6271851271 6531978387 6392448373 3269104323 0237409616 6673814238 6905353323 8578454541 6554526965 9422896796 9501656213 6144987884 6849560513 2313339686 2503535022 1181149063 5485693771
• c₂= 634745814 0917447050 2301727006 8779600634 1653539081 9879323462 1793839520 0215615005 8496913440 0608206004 8412238883 8421443254 1598273272 7291419842 5752742518 5590058053 6351069651 9872123727 0706544547 1273877147 8425198330 7711571616 0064078673 0304090803 3765448193 0314105346 1692765289 0802356332 1286573176 4343353617 2091505411 8024828604 3790162188 6360882380 6005194231 6423519605 8342738709 1191711643 2095165140 3691967935 5005233256 8345313904 5922120867 6909055823 7050819999 4717513988 6585484680 0177882916 0749471812 3915183318 3792879293 6090986201 3797790231 5557750185 1903780834 2507204387 4269803441 4949579941 6235168248 6383995737 3891539487 3093896486 9884287390 3465865700 5666923684 5287889793 4952924469 5204009198 1336419299 9506482573 9254612683 5976852296 6018037591 9523173192 4959212104 7099281149 1074684651 5673208866 0836774675 7592283681 5854060492 8995085070 9136345339 1367405667 4906398800 8423131390 8203501174 5300980373 6521410558 5759380379 9432295015 5321815339 6465818615 0443266250 2764465306 9602650810 3041426481 3016667326 5808791136 8101834950 4976626856 0051881800 5431615325 3492250317 1989673203 5848193966 2624513332 1742328658 7030017774 7102070223 8190124401 4971684120 3682729423 0935305602 7127088104 2183335975 9206001345 7583325123 1070734957 5077762921 7292890298 6574549945 3204490281 0539085843 4958373248 3003301734 0959165720 2284929060 6500045546 7090101200 3987361805 3563082696 7784894443 9505030002 6693425370 5893485793 1996419430 4128916878 9850081915 9697573545 0148878410 4341018299 4800441883 4558494904 4808689494 0419031851 0358634015 4367660050 6072694535 2984180620 5087889117 1180512485 8752238724 1520555422 8345380956 4328641189 2831480980 8610881228 1289507352 3245636178 6872148022 4424723004 0584181642 5210450391 1521648076 1522799520 5331227059 2264401654 2292137835 8283752796 7477173659 1544481988 2002512900 2074310714 8792003553 5052964870 4832149599 1645109960 4851052790 1991886272 9778181910 9779109162 6039712682 5648876541 7575724359 3130256351 8349544618 0266597214 8045619571 7493291792 8821189199 1656488958 2961215698 8182070736 0466117053 5918155967 5198471772 4259869319 5951134252 8671939508 2383307262 8501112208 3160344089 8230858912 6653608434 4861547965 8695625658 3514722995 1154539259 1420803443 6087565953 9314981148 6616380815 7644512169 3812953862 5036451424 5489919515 6774171432 3965792238 1806923841 2842985209 8679155817 9459949381 3095987798 6979782258 0566101769 1784016212 4693738080 4273318840 6708937437 5216895092 5621320414 3044203993 0139268321 8765953287 1496058542 5313716434 9966974291 3590384030 4231503838 5247940864 4010834417 4321434187 9762349431 2712618396 7738495321 4919599038 7277408263 3491326852 8364820002 0697318468 1605060661 4148061727 0156565428 7465616609 2098767775 7134092116 6135852738 3466121274 1059995734 9780274540 3199756296 2554423842
• c₃= 324935040 6550427906 7916297997 4313500830 5897046006 8683460877 4270325139 3672703258 9793096078 7896359142 0309234894 8180815801 0933901023 4160222178 3355922583 6655957830 8472907211 3939147775 5350803928 5736307934 2381216570 1362299402 4597044814 7962950317 8586668735 7560305835 4440838659 3151942025 1026093954 6659574574 1429982684 6106262674 3435276587 6548998918 4605120641 9913691689 0465982175 3407923158 9676258724 1971194273 1899936935 6828689566 2815062573 4479954359 8024880474 4037521564 5639777614 0615244698 1631732318 0658969385 9087226800 7074522259 0106100853 0755605684 3659038427 0443556080 0231550315 7091036653 5487994120 0777539201 9711362712 0011169424 3774420485 7831481785 8727046417 5682509930 8597963587 7688859294 5881516468 3994438384 9770038649 5529827869 2857598344
• c₄= 61650771 2886711411 8720655374 2329343966 7110833769 5061870765 0923216136 1089075132 0838246741 5628852258 0900405945 5597807041 4072387816 6229099698 7518245643 7872858000 9118599082 7313936461 8628672499 9046390038 3163219605 7368950561 7980454503 4975940007 9518354629 2951265012 1069236264 1742513202 9762418282 0655537991 1954146086 3017068296 3237659557 1875338439 1286977671 3350463340 5283646005 5984978530 1640671753 4299915683 7620616246 9565131514 0037305816 3565162385 1597847323 6646036556 6151936316 1535702073 2721804186 7506726850 7745262995 4734775499 1393956039 4483790829 3850033877 4180170583 2134893368 6260148981 6635914170 0798778163 5337500167 1210391557 0654758923 3793714280 6364632629 6711023828 5148300312 5712930413 4855932320 7503809339 9510347449 6062649345 1198936933 3272620542 7220625011 7557662198 8975819611 8292381381 2775091111 0392843182 8825420708 8191544836 8693951853 4874786556 0100289685 6368696884 6469868305 4912482453 5423272439 8763365402 6792010225 7521300641 5655078392 4224750921 3839910631 3476430817 9106513089 8130948325 3946951595 0188556926 2424715664 0448329395 7488825494 1886709935 8569890446 4297069412 4373816762 7853187185 8455295334 7520371510 4159244722 6600507220 2841527771 5349538009 0220222358 5997029335 7248735905 1252664095 3543504687 2399245909 1906712147 4692399451 9884089078 9216641482 7314375418 0203008397 9239561863 2175535936 8961578862 5496014046 4458257515 5342358401 8149064416 8227343042 6996117952 1282512710 0025745497 6758754352 2556954198 2901256514 9517759549 7635651128 0874948621 6793940196 3284279667 2070387510 2360673610 5612440541 6731607941 9221359035 5989248000 5147083534 6733018632 0308886938 7875998030 5473789354 6969794463 3676772946 5599596629 0830396678 3772077491 8617661689 1468871880 4287243287 9919864709 0189295306 0552595964 2351792457 6368714191 5230919080 0567239412 2160038358 4043843647 2387820629 3537340718 1792257205 9476891145 2923710280 8110972727 1748665664 0623485164 5076173670 4183186896 0605676449 7684049031 6346757375 6239263772 0780598926 5061294227 9901914601 8531362382 5165964560 6301603280 5385207716 8564737307 4808313508 1527492517 7091683220 5835295767 6961441347 8206998493 9720363438 2664539837 8132266219 4059283690 5525718044 7867003870 2086241302 4335714752 6643559825 9160979537 1749443543 8876016087 4739262928 8204220978 6496429309 3532224082 7746601823 9929912106 2571204307 3225323667 3120892206 2333751807 9891879430 8978226747 2648281925 4924361385 6220357084 1625585835 8288499722 5560672440 7419058102 7263791904 9161488980 2022705338 1293430544 1899458572 8716961265 7220638537 9517656396 6798699112 0464665798 4203579648 1043885913 6991550041 9382888672 1558657571 4743250774 9528190176 4884831005 9558811971 7394602613 8620290150 1753265429 3294800885 5708705241 1872321286 2025139126 6876836343 7533172179 6847117477 6362642010 0708707013 1238971404 5946983722 1335167090 2137353450 6022764117 7347796467 2232017320 1827118572 8701671295 2283994041 7559473595 2765471905 0047028305 7143115930 4263866867 5999896850 9847850904 3486622402 3222096085 1181572464 4438256890 3868179708 9111226364 5512851055 0585308694 3198874301 3957280900 7790581461 1226252669 7930260014 7035684363 6814617437 1366069017 5377283199 4044733067 8226871470 3138595610 7798603740 3794347567 5524095304 3144600324 0123864174 8332106097 1031671977 4902762043 7902629070 7757809060 7705267842 8920631582 2393556820 2844674508 9192604103 7157459605 8302386923 5989548841 3353317786 2244359592 3423997092 1374463654 3271999353 9619499731 8867586707 3190283016 2888099711 7662507700 4435324005 2502830234 9913407854 9091453796 0112050295 5156871886 2160374242 0470197282

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 ≡ 23 (mod 63)
• Q(1) is not a perfect square: it is ≡ 5 (mod 64)
• Q(2) is not a perfect square: it is ≡ 31 (mod 63)
• Q(3) is not a perfect square: it is ≡ 61 (mod 64)
• Q(4) is not a perfect square: it is ≡ 39 (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 = 2 4164216012 8623747637 8281150737 2832135663 0076065267 3624566441 6161923578 5441807834 6437547506 9447237569 1907166980 0936825387 1148464014 4613448702 3004504413 0602205028 6837889464 0696713736 3467251714 8616060827 3892709280 2009046836 6908322212 9781256668 7550160638 0629972845 4176138349 8847243178 2810320303 6797564816 4548019259 1721740414 3247054552 6933208461 7155327816 3201641627 6600400781 6280091836 4628859133 2714635564 0581485558 3908003168 6578111947 2999283014 2834926527 4622511990 6803162282 3065597511 0106853449 8244841571 1732372135 2829704456 4497449081 9706458104 7758196257 3076887997 5437863393 9022866254 7164769557 4860172007 6920833973 8659517563 9498139446 5817319161 8028692882 6798086208 8911671745 2667669635 3051008182 7259327553 3207369932 1620732397 1675435186 1513322607 1644189687 2111643008 1864439131 3528202916 7745493917 2435737457 3402146301 2694161752 2364330559 2420461241 1972889336 3204745634 1910174026 9738359822 1473061396 7886780531 5794715505 3219269036 6627610239 0671119031 5754730654.

With those constraints, the unique continued fraction is: {0, 1, 2, 2, 7, 1, 1, 4, 1, 1, 197, 47, 2, 17, 2, 5, 3, 2, 1, 4, 3, 1, 1, 1, 7, 2, 3, 1, 3, 2, 9, 1, 1, 23, 3, 12, 3, 2, 1, 3, 3, 5, 1, 1, 2, 1, 6, 1, 4, 1, 1, 1, 1, 2, 274, 1, 1, 6, 1, 5, 6, 2, 1, 27, 1, 17, 5, 16, 3, 3, 4, 1, 27, 1, 18, 1, 3, 1, 368, 13, 1, 1, 199, 1, 8, 2, 1, 2, 1, 1, 7, 1, 1, 1, 3, 3, 17, 4, 1, 7, 1, 1, 5, 1, 2, 1, 1, 1, 12, 9, 12, 2, 2, 1, 21, 1, 1, 1, 1, 2, 2, 3, 1, 2, 7, 2, 2, 28, 1, 8, 1, 1, 4, 3, 1, 4, 1, 9, 1, 5, 1, 1, 3, 1, 1, 2, 1, 39, 1, 4, 3, 3, 2, 6, 4, 1, 2, 2, 7, 1, 1, 1, 1, 4, 5, 1, 1, 3, 2, 3, 1, 11, 1, 1, 638, 1, 3, 1, 2, 14, 1, 10, 1, 9, 38, 1, 1, 1, 113, 2, 2, 9, 3, 2, 1, 1, 6, 2, 4, 7, 1, 18, 1, 1, 11, 9, 1, 20, 2, 3, 16, 1, 4, 1, 53, 4, 7, 2, 1, 6, 1, 1, 9, 108, 3, 1, 1, 3, 31, 15, 2, 16, 1, 2, 3, 1, 7, 6, 1, 1, 8, 4, 1, 1, 1, 1, 1, 1, 2, 91, 1, 2, 4, 2, 1, 1, 1, 1, 8, 20, 2, 1, 5, 1, 1, 2, 3, 1, 5, 4, 19, 1, 10, 2, 3, 1, 6, 1, 1, 1, 1, 6, 1, 2, 1, 1, 1, 1, 8, 388, 2, 7, 2, 1, 7, 1, 15, 1, 6, 1, 2, 2, 19, 6, 7, 1, 15, 2, 2, 12, 5, 2, 11, 6, 1, 1, 1, 120, 2, 2, 2, 17, 3, 1, 3, 2, 48, 1, 1, 1, 6, 1, 5, 1, 3, 8, 195, 1, 5, 1, 4, 1, 115, 4, 1, 1, 1, 5, 2, 1, 2, 2, 1, 1, 5, 3, 14, 1, 2, 4, 2, 1, 6, 12, 3, 2, 1, 2, 1, 1, 3, 3, 1, 2, 1, 2, 3, 2, 1, 1, 1, 2, 4, 1, 1, 12, 2, 1, 2, 2, 5, 3, 3, 1, 1, 5, 8, 1, 2, 1, 113, 1, 12, 1, 2, 2, 1, 1, 3, 4, 3, 1, 7, 1, 1, 2, 2, 1, 6, 1, 1, 2, 2, 10, 1, 1, 4, 4, 1, 1, 14, 20, 1, 2, 64, 7, 14, 1, 7, 1, 1, 6, 1, 1, 1, 2, 2, 1, 9, 2, 1, 4, 6, 3, 156, 1, 11, 1, 5, 1, 2, 2, 10, 8, 2, 1, 1, 3, 22, 7, 79, 4, 1, 2, 2, 1, 1, 1, 1, 3, 1, 48, 4, 1, 3, 1, 7, 4, 2, 2, 1, 1, 8, 1, 12, 11, 1, 1, 1, 12, 3, 1, 3, 14, 10, 1, 1, 1, 1, 1, 3, 1, 2, 7, 1, 1, 2, 1, 6, 26, 7, 8, 15, 2, 4, 3, 13, 38, 1, 2, 4, 3, 1, 1, 114, 1, 15, 28, 5, 5, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 3, 3, 25, 6, 89, 1, 16, 1, 4, 5, 1, 4, 5, 9, 2, 2, 22, 1, 12, 1, 72, 3, 1, 7, 1, 5, 1, 28, 1, 6, 1, 2, 1, 2, 10, 2, 1, 1, 2, 1, 1, 12, 1, 418, 1, 1, 7, 3, 5, 1, 2, 11, 4, 1, 2, 1, 9, 1, 3, 2, 258, 4, 2, 2, 2, 21, 4, 2, 35, 1, 2, 6, 1, 2, 133, 1, 74, 1, 4, 1, 1, 1, 17, 1, 10, 1, 7, 1, 1, 2, 1, 4, 1, 1, 3, 2, 7, 1, 2, 1, 4, 1, 348, 2, 16, 2, 9, 5, 1, 11, 1, 6, 1, 13, 1, 2, 2, 1, 66, 3, 1, 1, 7, 1, 1, 3, 15, 2, 2, 1, 1, 1, 5, 26, 3, 2, 4, 2, 9, 44, 1, 55, 1, 1, 1, 1, 3, 2, 2, 1, 1, 1, 3, 2, 1, 3, 5, 1, 2, 3, 3, 2, 6, 3, 2, 12, 1, 1, 1, 1715, 1, 4, 1, 1, 6, 1, 2, 1, 2, 2, 2, 1, 2, 2, 17, 5, 30, 3, 2, 2, 1, 1, 1, 23, 1, 2, 11, 2, 2, 2, 3, 1, 8, 15, 1, 2, 2, 3, 4, 1, 6, 38, 3, 2, 2, 2, 5, 1, 2, 2, 7, 3, 1, 13, 1, 2, 1, 1, 6, 1, 1, 1, 1, 1, 10, 2, 3, 1, 1, 149, 2, 7, 1, 1, 1, 10, 1, 1, 1, 1, 4, 1, 11, 1, 3, 1, 6, 1, 5, 1, 3, 2, 6, 1, 1, 9, 1, 4, 4, 3, 90, 2, 1, 2, 1, 2, 3, 4, 25, 1, 7, 1, 7, 9, 1, 10, 2, 2, 1, 2, 1, 7, 8, 4, 3, 1, 72, 112, 2, 17, 2, 2, 11, 1, 6, 1, 2, 1, 3, 7, 2, 1, 1, 5, 1, 1, 7, 4, 6, 1, 2, 1, 2, 3, 1, 1, 1, 1, 1, 22, 1, 35, 1, 5, 2, 3, 1, 1, 5, 2, 2, 2, 4, 13, 2, 2, 1, 1, 1, 1, 48, 10, 1, 1, 4, 6, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 16, 3, 1, 32, 25, 4, 1, 1, 4, 1, 10, 10, 17, 1, 1, 43, 1, 8, 311, 9, 1, 16, 1, 230, 1, 2, 2, 1, 3, 4, 1, 1, 3, 1, 1, 2, 1, 3, 1, 3, 15, 1, 5, 2, 5, 1, 28, 12, 2, 2, 4, 1, 4, 4, 10, 2, 1, 1, 1, 8, 25, 1, 3, 1, 9, 1, 5, 2, 5, 1, 3, 9, 4, 2, 46, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 61, 4, 3, 4, 1, 3, 3, 12, 1, 6, 1, 6, 1, 3, 1, 1, 1, 12, 1, 3, 2, 1, 2, 1, 21, 1, 3, 1, 4, 1, 1, 4, 8, 10, 1, 6, 1, 19, 2, 3, 4, 1, 6, 287, 12, 2, 81, 138, 2, 11, 3, 1, 1, 1, 1, 1, 2, 1, 30, 1, 1, 1, 27, 1, 22, 31, 1, 1, 4, 3, 1, 10, 127, 15, 1, 23, 1, 3, 1, 25, 1, 8, 1, 1, 2, 2, 1, 1, 8, 33, 2, 19, 1, 1, 2, 10, 3, 3, 1, 2, 1, 4, 1, 13, 1, 1, 5, 19, 1, 1, 1, 1, 1, 3, 7, 3, 1, 3, 2, 2, 3, 1, 1, 1, 10, 1, 1, 101, 1, 2, 1, 1, 1, 4, 13, 2, 1, 33, 9, 2, 1, 1, 20, 1, 2, 4, 1, 88, 1, 2, 88, 1, 1, 104, 1, 1, 5, 1, 1, 1, 1, 2, 2, 1, 6, 4, 14, 5, 1, 1, 12, 1, 2, 1, 1, 2, 4, 17, 1, 1, 4, 2, 1, 2, 3, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 40, 2, 5, 3, 15, 1, 2, 4, 1, 5, 1, 7, 1, 2, 4, 1, 4, 1, 22, 1, 24, 1, 9, 1, 4, 1, 6, 1, 4, 4, 2, 5, 7, 1, 4, 2, 1, 54, 3, 8, 2, 1, 4, 3, 3, 1, 287, 1, 6, 4, 1, 3, 1, 1, 5, 1, 25, 1, 3, 58, 3, 1, 2, 5, 1, 2, 2, 1, 81, 2, 1, 2, 1, 2, 7, 1, 10, 1, 5, 2, 1, 8, 17, 1, 6, 3, 3, 1, 2, 1, 1, 2, 1, 4, 1, 3, 6, 1, 1, 4, 2, 28, 1, 1, 3, 3, 1, 6, 6, 1, 3, 1, 2, 6, 1, 4, 11, 1, 1, 2, 1, 1, 67, 11, 4, 1, 109, 4, 1, 2, 22, 16, 2, 1, 8, 19, 2, 3, 15, 1, 64, 2, 1, 23, 1, 1, 2, 1, 1, 2, 5, 2, 1, 2, 1, 5, 1, 1, 1, 2, 2, 5, 2, 2, 1, 8, 1, 14, 2, 1, 1, 10, 12, 1, 51, 1, 1, 30, 2, 1, 9, 1, 3, 1, 2, 1, 10, 2, 9, 11, 9, 3, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 3, 1, 28, 1, 2, 7, 1, 2, 2, 2, 9, 1, 4, 5, 1, 3, 1, 1, 19, 1, 1, 2, 1, 17, 3, 1, 1, 1, 1, 2, 1, 31, 3, 1, 1, 2, 1, 1, 1, 2, 29, 1, 7, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 163, 2, 2, 8, 4, 1, 3, 1, 3, 8, 6, 4, 1, 2, 7, 1, 3, 2, 1, 1, 1, 5, 3, 2, 6, 1, 11, 2, 2, 8, 1, 2, 2, 1, 2, 1, 5, 1, 1, 3, 1, 6, 1, 2, 3, 2, 3, 1, 4, 4, 1, 6, 4, 2, 7, 2, 1, 1, 8, 1, 72, 4, 1, 15, 3, 2, 7, 3, 2, 2, 2, 2, 1, 1, 7, 2, 1, 12, 4, 2, 2, 1, 2, 1, 3, 4, 6, 2, 385, 8, 1, 3, 1, 1, 1, 16, 3, 3, 1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 9, 2, 2, 28, 1, 15, 1, 3, 20, 1, 9, 1, 1974, 1, 15, 1, 1, 1, 1, 4, 1, 7, 5, 1, 2, 23, 2, 1, 1, 1, 1, 1, 2, 1, 6, 2, 7, 2, 9, 28, 1, 4, 1, 1, 2, 1, 3, 1, 4, 1, 1, 1, 4, 254, 6, 2, 1, 21, 6, 3, 1, 1, 4, 2, 11, 2, 1, 1, 1, 7, 1, 4, 8, 2, 1, 12, 1, 5, 14, 18, 1, 3, 1, 1, 1, 1, 6, 2, 3, 3, 3, 2, 1, 6, 1, 2, 4, 5, 8, 1, 1, 204, 11, 1, 1, 1, 1, 15, 1, 1, 28, 1, 1, 75, 25, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 3, 3, 2, 1, 3, 15, 1, 2, 5, 1, 7, 1, 9, 30, 2, 1, 5, 1, 14, 1, 1, 42, 4, 2, 1, 12, 2, 1, 2, 1, 6, 9, 1, 1, 8, 1, 7047, 1, 35, 1, 11, 1, 1, 13, 2, 1, 3, 2, 2, 1, 1, 1, 25, 1, 7, 1, 9, 2, 4, 9, 1, 3, 1, 14, 2, 1, 3, 1, 3, 2, 1, 2, 2, 3, 5, 1, 1, 1, 3, 2, 7, 3, 4, 1, 15, 3, 4, 221, 1, 5, 4, 1, 1, 1, 2, 5, 31, 1, 3, 1, 1, 7, 1, 3, 1, 3, 1, 1, 1, 8, 1, 8, 1, 1, 244, 2, 6, 5, 106, 3, 6, 8, 3, 1, 8}, giving these values for u and v:

• u= 1 0619171016 8370477404 9154813781 3950259857 2887981991 5169279340 0485213903 8170550742 6811890330 8864315549 6225535726 4224249676 9139508004 7551921044 3243520981 8086835754 4869747482 5553184279 9581744644 7075340964 5816510520 0885177639 1568844916 6348740795 7545638039 0838029050 1117948251 0835232304 4354779716 9671886400 9659445948 2925157599 7963147841 8437931145 5083425527 8028941382 4491298061 3242257020 5334953188 5799632491 8889376984 4365701118 3271400097 0143047309 2297710596 4722889028 3413955797 9505855905 8806864336 1118435296 4489502505 0816269586 5858117997 8421841139 8639561229 4290916608 3176116891 3553150218 7981694388 8516812769 4827593694 9741977798 3459554822 6153048722 7950601119 2091485427 7601975420 9810418480 4872586514 1287664013 0519068431 5166299202 9118086816 1066661092 8410642443 4290145134 5619165416 3802470699 6012536918 5212971356 3155883298 6228142071 7563012630 3351836880 6073134226 8036093528 4317222642 5357429288 8117613680 2271918225 7534908241 7174543841 0943668914 0885433939 0242443234
• v= 1 4920269299 8936002909 3599784336 5625041418 6929120681 5815182287 0138377703 6956779266 2814806319 5762154238 4703256496 2524482321 8000961294 2563233688 2898935109 3584785689 2296648272 9398904396 0757351294 9972770207 6398980689 9577420388 2985298124 3010419181 1790151876 8785534432 1155205433 9883695234 6903566390 8053504854 2178482543 6367018455 4729293043 5410609709 7368746792 2077907515 2038587083 5295041636 8903023011 6065287729 7890069961 6698801879 8623012495 9823306706 0727540148 2653787878 8927121093 7911836894 5366049962 6929451348 4315004725 7168124546 7778319854 7117959875 1899787678 5625451041 5340701376 7445568303 8734373348 3526687565 3613343172 9459369970 6553617265 4591920484 6867636174 1926966892 9046863994 3926419223 6433741167 1549591269 5822808618 3821177539 7488215268 1581535979 3198205662 3425203263 8381221674 3015216365 5223357438 8923885108 0715946535 0591217368 3803217235 0627583924 8281768250 2124045861 3944327802 5417493499 5064930807 4612311601 2252712270 4657422568 4222290867 6544317515 5015155899

… as taking one more term in the continued fraction would give a value of v of 6 1384803451 8375760084 9070876689 8738928277 1869098837 8128326311 3558142005 8380850809 6382758816 9496008617 1268487429 4412128531 5092445718 2363158773 4860718306 1275938336 6978080669 9594719100 5065640117 3015349970 4231548964 5055216889 4190214133 5983048172 8744372250 9773645818 3033283653 3568739940 7682955896 9327537384 1352799214 2778046214 7383071279 4963936882 1980433397 8158964056 7078686165 6470096372 9124464054 2530380893 2288444478 3388141711 0123192259 8536961659 9883507479 8124405990 6627908003 4791322733 8258010029 0000883590 5923608950 0350243993 1527235139 1817949205 8058852932 6381908832 0294353010 1544867265 3334866206 5222779200 0158516966 2387504574 1403650194 5837688768 0023575828 4576104305 5314389331 4240322394 9091000314 7791092211 4758444542 6248698922 5587468476 9517517620 6153583290 7145470469 5639459988 7683597266 0228268221 9269006974 0952202601 4368318782 3730585019 0746699366 9348187775 0550358981 1391353218 8831158270 4363091463 7648282533 8063642815 9172843473 4517242318 3988043855 3358527337, which is too large.

We also need to calculate d = floor(c₄·v/F + 0.5) = 484811831 1545113846 1662452941 2845261775 2451046417 3152735585 7682888536 8947277034 5517017685 8522549376 6581317467 0184612559 0922489267 5985974641 8520449632 2248088201 7309532243 7368269484 6871839748 2985624293 8557793788 7211816830 2064177028 2617177366 6955903104 8046314972 7333039389 3521353627 6764654602 6988840725 1316923282 5622059522 6244569464 4296465917 9671648162 0606487425 6107484840 2388945808 4070598708 9185004613 7040203021 4861872617 7808848581 4881188468 7252455317 2147981598 7565888732 6677004302 1120453628 0906548033 1753275951 4490137203 0487661487 8999536512 6793310369 7610756347 7307130211 4094624984 7176219813 4158200845 5098226358 7946043292 3334754294 4777378082 3983411310 7991800642 4934994878 3082842553 6083917625 5207145696 5039798017 1243369214 6722114862 3420775333 3508798821 1446320839 2055578528 6749910810 6260828256 9749672714 6875740195 4705423812 6940815246 8745000163 3266474375 8464188132 2470302760 5997099324 9341071284 8766249034 8513347312 5127397660 3435840961 1947297629 8211780097 3410537638 0088230416 6710141553 0135835621 5008025925 7417192384 0718131273 5326515067 2627024768 6783634180 8505856300 2231756125 8918381945 4177598958 4881661507 4701737332 0945369258 2770529090 3988217504 3846557566 3134984864 2873862774 1763880802 1754346661 0307912063 2323135876 2778317188 2236160806 1101131473 2671967672 1955930759 8479315323 3043192632 8439390262 6667207754 6809746015 3259211737 7239434939 2497724791 8150799040 9205237601 3536965220 5908489819 3498111281 3544463404 6862763659 4188184926 1663327144 0822449525 0981249980 9390655493 3121228961 4024408944 3592221605 2126015145 9630596349 4872199591 3599983759 3156212885 6128801074 3892449646 3365261708 0990843743 0355069095 9670869727 3832493184 3657925791 4839734456 3230226380 9613748845 1798857380 6018944413 6139709510

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₁= +1 4920269299 8936002909 3599784336 5625041418 6929120681 5815182287 0138377703 6956779266 2814806319 5762154238 4703256496 2524482321 8000961294 2563233688 2898935109 3584785689 2296648272 9398904396 0757351294 9972770207 6398980689 9577420388 2985298124 3010419181 1790151876 8785534432 1155205433 9883695234 6903566390 8053504854 2178482543 6367018455 4729293043 5410609709 7368746792 2077907515 2038587083 5295041636 8903023011 6065287729 7890069961 6698801879 8623012495 9823306706 0727540148 2653787878 8927121093 7911836894 5366049962 6929451348 4315004725 7168124546 7778319854 7117959875 1899787678 5625451041 5340701376 7445568303 8734373348 3526687565 3613343172 9459369970 6553617265 4591920484 6867636174 1926966892 9046863994 3926419223 6433741167 1549591269 5822808618 3821177539 7488215268 1581535979 3198205662 3425203263 8381221674 3015216365 5223357438 8923885108 0715946535 0591217368 3803217235 0627583924 8281768250 2124045861 3944327802 5417493499 5064930807 4612311601 2252712270 4657422568 4222290867 6544317515 5015155899
• z₂= +257354046 5835502623 7336259032 8108534668 9244050851 9020829077 8825720706 6591929054 4870478457 1081574167 5257249038 7196015752 0331241928 1685769873 1718266854 1538936204 7559945157 6710260403 0877551688 5312240250 8455085491 2942775492 7729681030 0337582838 1620812495 6884913217 0935476815 5050793141 8847507502 4165117408 5353926642 4853314379 5085681083 0364511026 6758454457 3002039500 5763868694 6751801213 4184363693 5438065986 2859113773 5714719277 7517385688 1755409836 6716050772 5655533311 5902879830 9497947552 9583180062 5864795258 7892574611 6177697964 3316148325 6797465647 9252589709 7701490473 3044870734 5743848198 2259137018 2853121140 9753428910 9492218699 5572476270 3554241188 2909516739 8816393966 2915280672 5969670630 7826234035 5078367083 5716247794 0655514429 7909257253 4955502537 8808529353 7340062041 4392045208 5783379192 8878016034 0194505944 7661562379 6163106125 6448438732 3647507486 8969548818 5146589838 9781728299 8883783118 7141762858 6417816591 2256883830 8830497039 4791984863 6163049745 1417636854 5018875338 9956351297 2485939937 9742745965 9218228549 3869635833 5147620583 9792591984 4890923680 1372236288 4120856237 9462097276 2535713114 8203908538 0333028128 1276794126 4531697207 6834287262 1876404270 1779864105 5410327233 4276980486 2706440334 5845507412 6675298361 0067592964 5369092970 0539713464 4230340046 0627989049 3577827211 7157743085 8383167125 0445745999 2504640337 9719538626 5358476979 4421851020 8960224093 7520594190 7061903832 7737202758 2587434757 2229090549 1988827633 9629376162 9690657721 8009654286 9791328190 7672799060 2452944296 8443790234 5594733448 9499262133 0244233172 2248179746 1911169881 2900804756 5015612117 7038330658 4440022930 6660043330 7697010808 0255316909 0547676357 6972700705 6469454241 2507096609 7168430284 1159091096 1126439269 9636919331 1016854711
• z₃= -491892664 2104040544 0882696654 5898024793 9060817139 3251818314 8171271782 5962867534 6786890066 6458625807 3579073570 0650411921 0179206295 3878366937 1239842059 0176339121 1368910927 2203362993 4332086927 8255973823 3609020354 0199716651 7465189164 4568429708 0274446553 3384677796 5117168600 4729851030 4510146337 6124144172 2774109342 3943567837 4513152770 3494513254 4507457400 6589351448 2919883334 9905930001 2167701647 4410371013 3199412085 8147760127 5947230686 8253608518 2330014440 3781964674 3323152813 5692532366 9053512615 1411308428 1499026698 8804269031 8177786069 5742219475 8935258730 6693035167 4661325356 4702997458 6515486235 9031452405 8740015531 8373981385 4140920250 9347583740 7948617914 2696446458 6844430709 4663365925 5578504167 4500839049 7608136042 2555755845 2861654297 4114714780 6385428619 3675430921 7193917060 7199784488 5212966306 6667446864 9103028872 0460493724 6830412942 5856651864 2953486149 8027048345 3267599540 3687009463 9857811090 0279358918 3732095710 0438659237 1635720414 6080998894 0892089560 4617888279 9323256679 6782722453 6067779481 2515374906 1499363260 2215376449 4609046212 3855219617 6449421516 6912782232 9061397241 3964875896 1208883319 9540357428 2597430421 3117587877 2405704795 2264952895 1902645390 1139565969 3534018313 8832758150 8638645166 1095351152 3875080773 7393095042 1541604566 9821188119 0281041539 4269508993 3730930084 6256016062 0766905219 5468569109 0494611702 4819300692 6995867354 7262081406 6141514684 5859151818 9183770858 1489141946 6343462664 6235465194 3218204811 0058600695 3723276822 2441553466 8085855891 3028632190 4541953552 1863097699 2018063340 0150980114 7721789281 9223935293 7643545444 0591433700 5099982784 7434053832 7660223739 8646869255 1663810390 8125927284 1820221757 9008321919 4370828475 1134742372 2792463456 0702861528 3863416411 9539708168 8323739236 2653643559 8860165471 9501794819 1923716894 0940987650 5131902061 9614867869 0171312209 7745050307 9854199319 2540257345 3046177477 4078148914 0548423410 9440666757 3599787561 3090723433 1866206853 1652607171 5093752549 9540740755 3260104732 6735969493 3803436216 4857151019 0079815963 0897307601 9951890333 7190916600 1926807720 7224781276 4000274126 8189480921 8182047745 8176182048 7988779969 9482421397 5169935565 5546448158 3876645046 4213217055 7362598716 4720421001 8990555305 6376495342 1659004567 0049966693 3330754353 4006033739 2017779050 4683522755 8174200655 9706961134 9867975244 6119987153 5179323341 9133723277 7838315150 9395465687 4846163836 4509342599 7559497631 4543529056 9589823778 9845763341 5190519617 0220957899 4352257765 5300356325 4287979695 0306465587 6310595469 8032115562 7001488498 6969943143 9972353607 2828819180 6647259608 3275846686 6700060154 2474551625 5104629591 1950478038 0075687459 6742310659 1229544362 2877766267 0827093709 6950407383 4488803629 8406391460 5330618924 7700126507 5326747848
• z₄= -484811831 1545113846 1662452941 2845261775 2451046417 3152735585 7682888536 8947277034 5517017685 8522549376 6581317467 0184612559 0922489267 5985974641 8520449632 2248088201 7309532243 7368269484 6871839748 2985624293 8557793788 7211816830 2064177028 2617177366 6955903104 8046314972 7333039389 3521353627 6764654602 6988840725 1316923282 5622059522 6244569464 4296465917 9671648162 0606487425 6107484840 2388945808 4070598708 9185004613 7040203021 4861872617 7808848581 4881188468 7252455317 2147981598 7565888732 6677004302 1120453628 0906548033 1753275951 4490137203 0487661487 8999536512 6793310369 7610756347 7307130211 4094624984 7176219813 4158200845 5098226358 7946043292 3334754294 4777378082 3983411310 7991800642 4934994878 3082842553 6083917625 5207145696 5039798017 1243369214 6722114862 3420775333 3508798821 1446320839 2055578528 6749910810 6260828256 9749672714 6875740195 4705423812 6940815246 8745000163 3266474375 8464188132 2470302760 5997099324 9341071284 8766249034 8513347312 5127397660 3435840961 1947297629 8211780097 3410537638 0088230416 6710141553 0135835621 5008025925 7417192384 0718131273 5326515067 2627024768 6783634180 8505856300 2231756125 8918381945 4177598958 4881661507 4701737332 0945369258 2770529090 3988217504 3846557566 3134984864 2873862774 1763880802 1754346661 0307912063 2323135876 2778317188 2236160806 1101131473 2671967672 1955930759 8479315323 3043192632 8439390262 6667207754 6809746015 3259211737 7239434939 2497724791 8150799040 9205237601 3536965220 5908489819 3498111281 3544463404 6862763659 4188184926 1663327144 0822449525 0981249980 9390655493 3121228961 4024408944 3592221605 2126015145 9630596349 4872199591 3599983759 3156212885 6128801074 3892449646 3365261708 0990843743 0355069095 9670869727 3832493184 3657925791 4839734456 3230226380 9613748845 1798857380 6018944413 6139709510

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)
• - 1815711490 4496351837 6340525227 6445571889 2130126757 1014027096 1414237439 8826666649 4193171725 8447016791 4264101870 9784102949 5645606945 5750198104 4290199637 9853616643 6971843651 2691633346 9341797746 4948107322 0145016246 2701887703 8904280768 6410761701 5112622726 5193005029 9727271017 0983501354 1212983720 9375701228 1883816157 3648961001 9921099450 9018071877 7411895080 1691329502 0394988213 1975158050 5262010900 3079765952 8357345476 6109941839 5586575708 4408216945 7989467504 2250586860 0626941318 8814880508 3066489929 9968219190 6155996458 0396356867 6846273933 0740832547 8929050117 2323834202 0027194585 8114083320 2756203824 1793516762 3462318138 5622566839 2112992506 1309748266 5804925959 7095895248 0522342687 6795941299 2034128674 8211870107 5252898157 0942621692 6601994609 6546922979 7800714708 4851837958 5688542558 2809554693 6962396437 1475663599 6981214387 4860868977 4404797312 3366894702+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• + 1815711490 4496351837 6340525227 6445571889 2130126757 1014027096 1414237439 8826666649 4193171725 8447016791 4264101870 9611616755 5081400705 2769401533 4936578965 8864000916 3790739750 2143338095 5183565511 6848212294 8752783745 3252112306 3625622548 0703913903 0041327567 8374682254 6167785777 5296976608 6637909208 9295884512 1928821910 5450919047 9185781403 3482356711 0434090990 4845302593 3235017988 0080694609 6073826078 2861777515 4937307455 5799643813 8660679560 9308776290 8191566232 1054760618 0773347461 1785725224 6591336117 9017846825 2097642025 2419649319 6014970231 6450751647 6255092398 1250888390 3141108543 8837862366 5396080978 5938609942 1597929746 0809697275 7054570208 5552485434 2258045064 1007390350 0991238590 2212824939 7792456919 9037720756 1252991653 5336416878 5984884163 6345840497 4712874980 7676203569 0140898876 2584553236 7870613952 8484779761 0279166366 6657576747 5719223917 1211088131+ε∈(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.