Primality Certificate for (10268^2521-1)/10267

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

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 = 2 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₁= 441 6199297925 8030283740 7154271705 8088876483 0714983540 6560271509 0868313689 5455349610 5874237050 4354313599 7781455358 0403730113 0086016478 6380058900 1829165744 7032038837 5308784712 2203588385 3656987550 9444480578 7381416576 1344251595 1982371822 8505408659 8592380953 5279705063 6648072912 2762357260 3538414220 8182987920 8285809706 8254553861 8840722214 7820178390 9314223552 3814986847 7396604870 4110235021 5680910330 9788763478 1571660337 0607567303 1435676952 5716631485 5626713573 9498602383 3177527462 9652803333 5611644667 7869168711 2861398911 2857632729 8904739386 9924938224 8940467643 1638658782 5644207816 1706603455 7390523469 1439750092 7728357264 9649380202 1050175824 9050370353 3737550794 7249393467 2801647378 2719520822 1280938302 7998354549 7314420570 0976913455 4743887530 0119392244 0342540069 5572913195 9400845313 2066349310 6038796321 8030505211 2122563949 6970904292 4983104439 7541737355 2794410423 3660908757 9259488155 0030787395 4941119323 6654694264 7480897205 2944176406 4464856325 2454439690 6884527707 8914588161 7977873964 6913322149 4940296147 9383287450 5132850957 6175986946 6725092041 1571683657 4825112843 4623015976 4063253464 2439303309 3452970215 8048124499 1623290403 2500605045 8949816894 6155679371 4492729024 1063696973 3984766722 7221106359 4434324605 8270755894 4315939450 3508482373 5599670387 5408302430 3355126849 3039931963 7170847840 4764420886 2416524120 8518863726 5912261343 4082241671 9929205471 2913284976 2471539000 4713709532 6249843242 4090130091 6846800862 3647501626 5140629102 9402777011 2211687296 9453817215 2485851296 2395246730 3616370537 1061762425 7953484540 9719514310 9194249410 2862470679 4936437811 0198867520 7915446335 5413275929 1199158072 0628420275 4212746774 2163497662 6718137045 0586752735 3627954546 7604253666 6021915809 4495841089 8864065174 2063304985 0220592615 0206517770 9419761743 9266134809 7710918252 1075901037 6753434041 2500182645 3448267365 7048472787 7359906876 8428397493 6246347862 4322013473 3723762815 3553122013 8616462270 7989944601 4592626821 0344610333 7649555376 6534109263 7841125705 4807442890 1530012987 1098005793 3901472325 5273949564 4950021949 4723882676 8895358317 6384267190 4151121855 9777224719 3168896333 2524207585 5146669987 8325617234 9207452131 9579597497 6369022181 0607330322 0515468287 8937633097 2920723518 7348737144 2752002697 0418472563 5868186641 4655634221 6505750265 8024975348 5251447058 7616368107 0654390633 5039554730 8955759674 6088547429 8398196317 1028257535 7245480650 6493454527 4540518052 6657324103 0961812946 6849130142 8212013561 1824598678 1642788072 6118546664 4158648533 5661743570 1821903947 8046737361 1806664001 7845848359 0528942192 8476119338 3132129020 9493690750 8882703278 9990688672 6514899750 4739035467 3448976426 1987137669 4519125817 9458057128 1018725111 5765327166 3812396219 7658550919 5518344401 4857343544 0616475297 1553000921 2338212361 8659996189 4306380433 4752324475 1109968315 5189821163 3526089204 6553405145 3194951094 6437285679 5025654456 6538954561 6186125104 5528621960 4582173806 1574854414 8976852051 2423707753 6918512591 3607705008 1750653736 6675023629 0071894335 9078444542 5159285260 4039706108 1255631623 6745869219 7525185347 1927921415 4496279115 5357805103 9611788333 2023089562 0312046289 0790421878 3121496855 7567590230 3801026753
• c₂= 872 7811818770 8445656007 0376784653 2419652270 9116851901 5981208053 5482221810 6014500644 7378911352 6087368768 2065711737 7939548294 8017968279 1938354392 6855428094 7950226739 7291502406 3765082832 2641313894 7154644242 8030884758 9297272070 9142921040 9610522401 0647280833 4762725935 9518079434 4134597890 2951244123 3849213541 4641626399 0670801777 1294146718 4387852867 4277763096 2660700571 7484398386 7678659860 9724161306 8414829534 5637578627 2127664545 5419197307 3058906964 0161415405 5629678817 7408029473 3731739946 4583485354 2341822902 3280777117 2825269959 7002367415 7962542192 1114186505 5762981894 8599792354 8558311845 0068225054 7328787168 8655002578 9315110210 1289043547 8209283502 4974804332 4709652995 0835939329 3816693191 2478209879 6399343429 8043709312 6036622840 0399205127 9450188277 8722144545 9600365459 5979343504 2396492268 9552930018 0049198465 2772145859 7856633098 6248197100 5876000844 4732467293 1528889780 7097412540 2012549603 0984409933 4901185104 4361970045 0014381446 1781836796 1397889410 1933583616 1369210665 6860993974 3635422480 1819473833 6753370897 2632975786 4663798313 7118618991 9911352625 4412489868 8725066194 2923947159 5205257300 3743030754 6577262564 2777376441 1946575867 0098131423 8354465068 6441242445 5797070007 2978914652 9996497954 6690853422 5322492680 3713031257 8599895500 4971771367 7750024091 7373213882 6162371395 5515352830 6575468012 4216064934 0308452039 4946938750 0010439799 2627536526 5282770970 9659224235 3162293022 0681030286 0577677874 1334150165 9389586894 5220141571 7741677405 2342923235 4345333890 8463302401 8450265083 3338776700 0806738218 3768177745 5098360028 4966323166 8756475187 0125730644 0291601551 8763839189 1762908276 4321054554 9494147958 3355577082 9413373730 0808752797 4979666224 2753267708 9110241833 3890857492 1171312190 0470274296 6369470006 9126143145 4615351626 6010027589 4904712560 9789101558 1560500223 5180177568 9674640381 4093493655 9885777080 7459844616 7703287447 7902643749 5179186349 1222658599 9462527823 2489488555 2376331054 8783993569 7084660925 7289542278 2537733986 7848577964 7067528827 6377885929 1218613062 8996895845 6895747225 4466299893 8612038779 2790013814 1017601630 6561361918 3188758876 4087205405 8608697718 5204151147 3885345902 9100612063 2915346619 9848945561 3974604345 0014829967 3421874555 4241853594 1631530548 3844274524 0126564879 6684785846 5218387440 8631207103 0843528985 9521715700 6646364652 9592660140 9414048324 9044747926 1921304173 5907775386 4069157980 6896143121 6515979242 9099980217 8960532274 5937604415 4556137357 9812194799 7239309964 9147141640 6827502571 3236352192 4645740845 1255317199 0787048861 5485894060 5205309445 1039166150 6248646685 5736607225 2817802594 4015493086 5227043464 9524741987 9981254757 6665600077 8829290593 3672582929 2201445954 5150211429 5423345717 5462687379 6806867696 6397722605 2116973925 4395959361 6625803371 4508901449 3782917709 0601197695 4466937792 9680575062 3677200953 5973666419 5530221337 6188242757 1444020190 3110330968 9026290384 7518741734 9085787876 3826300744 9180683009 6040238003 4699818368 9132490068 5959979036 8083725227 6046578353 0472072006 6337626093 5473528692 2322752288 9838312345 5960040237 5657629797 4511114946 0670744302 0004310854 0422622573 7451018380 1368808297 7406528675 5220310233 9061373724 9874166620
• c₃= 7509803811 1969622285 2450511291 1558331069 3835402772 5924317536 4726309569 6266802771 0954244753 9844435121 2004770220 2485901950 8076181913 9439743152 5695799340 8776826001 0086481550 4177960137 4120578272 9591213277 3389577499 6249379855 6401535955 6484693107 2385036992 5766983886 1659920883 7260718041 0473486979 6092755851 6763849371 2789528240 1314255076 3856206124 2667409017 2243779856 2917282732 9848133727 5237276174 4455982116 8955000302 3263805211 0912339293 8933127429 7799049196 8688132417 2361793811 9854484382 6303165786 7563245280 7141311911 3406083738 6362815755 4857259356 9622940548 5230603596 4355647978 0172800387 1251914376 3938852877 7425167715 9002536583 2091215252 0186480341 4015372652 8663955270 6403844600 2987698672 5980158211 0081681214 6871718024 8702874803 9092601342 3199436547 8089726052 2488608352 4192626928 0025868507 7990693587 0731759193 3178510332 3930480120 7080386463 7098659554 4632515311 2987054821 8315246956 7066264038 9357146810 3166791507 0409574876 2992413291 5222288365 6985401069 6712915346 9709612997 0643998902 8156976111 6253526093 4586726710 1404326389
• c₄= 791 6907300989 3165693222 7992919776 9699326136 1392890903 7393880770 6925165700 8735339601 3455489917 5758114293 0064038799 4060172875 8164688296 7026430243 6207082686 4181305617 6284675275 4715037352 8381673174 7410450467 6412857418 8159612932 4510237554 9143666081 1451135853 1827206630 4773134636 0499341652 6767860392 2706741689 2245647261 8511820696 9320567562 3239713334 3180195120 6001773287 2432779419 2418073526 0026223136 4006806721 0880609036 5542904956 2607568696 0193418429 9334204402 7457339817 5142174380 6096989998 0958306656 9725096698 5944239615 2163346394 5870493962 5693793143 3819480486 8389281583 3330696585 8731365654 0280902158 2069605976 7242655376 1777134690 2914973584 9720952345 4697602105 1816500195 5235954365 7892645861 9544316897 2284787325 4706305635 1971953020 5363950680 0803094233 5489217909 5125817143 8969156740 0225672051 7073144542 2295084032 9034267063 8206813752 9341559001 9313694887 5038375845 4271314777 6126472329 8189961556 7136165452 1302614760 0307418822 2851242869 3041147302 0891690102 6944530014 8283115202 8413266573 7404766976 0981627348 2854445969 3860423774 2437408122 7026142033 3962032979 6984003521 9877861642 1664118550 8603262269 8335517821 0527894437 4486034943 3711777812 2509911034 8410610452 8096845607 1884432448 1536314451 5707471607 3546853596 8267930003 8649848187 5313275019 4205063602 4840511591 4149842900 5726981972 5351877637 2662959937 1480872915 1111725658 8723236671 7202091957 1856462840 0339879937 7275209371 5935364581 7545475241 5177544048 9484985862 0526861614 1169276666 1671552141 9824717539 7975305838 4640410950 4923173654 6223332720 1032897667 2509375314 7361548870 9189425076 7730092157 9890118061 3474893819 7947245260 8200515094 6534060753 8584204106 7837059456 9790824043 9308447676 1520550879 1017918698 7894376554 7319020342 1730992276 9025507287 9464663971 2043886020 6820483603 7362454642 1700723714 2161690891 9543236743 2221850132 3840342320 7175188904 2249761765 2421800286 9863057471 5232473580 7791703790 0763684075 7047587648 2638032873 8772696970 3431364420 9532125787 8870156910 4900880653 6079297445 3634314062 9555006049 3102484615 8944352502 4728803559 9876545837 3197561270 7026369706 9842739599 3424337808 0924211249 6666640153 2870700122 5065910041 1458781855 9967392145 0111680337 3886334740 8306107748 4886268682 0470866421 3192121591 3683909780 2357972794 0861490950 7872663785 9918159652 0432414266 3233000534 1739905271 2831221491 5314181097 5938131484 7114279480 6003647983 2147287507 1397530930 8071759675 0011296249 0214596897 5714559521 5599049446 2010516898 1598919179 6797268643 8339075725 7588480225 1918962958 4718713908 8556348546 7831183183 6377593568 3153746540 7991362531 9090533396 7592961869 8385569912 0568399185 5962465100 1540188016 4604749075 9532995312 0013182957 8738951150 3180864967 0364716315 8725661955 5867606417 3993209910 3029880868 6471322791 9072165354 0495367987 3843687330 6588008534 3898361436 2289219440 8957066656 7859031418 9155872207 1712527609 1630882140 8483295981 0400706695 7021051810 5546344566 2264729023 2656491129 6967729637 9150357628 0702314653 2773601794 6629569921 9027869399 9793345832 6917829138 0795861989 3058762956 8977055417 3183695752 6169445606 6113877364 6462784523 4037198110 6067625889 3824911717 1441833152 6464587218 3878487837 2638294935 3968599118 9083601601 1660574503 7743709554 4358985830 3475666262 0705371414 2541888457 8669579661 9647700142 8583371771 0670563102 0467602829 6963747148 9389141795 4664969130 0831641197 4789996023 0256307730 2253086243 3177177363 1284885183 9909653164 1837905579 7620122649 5473664022 3386334439 9797559878 6014256205 0625794244 9325992351 8656768495 1752983976 5221854266 5169649459 3094678257 6470546150 9039753394 8739762395 7923141094 1511347042 3218260590 0125307678 1794600575 2783010922 7808277079 0488607933 3723202452 7246831023 8060422588 5561644542 3044690274 3553635353 6314633167 8740142451 8908432491 5924163168 6099575279 6420932058 6013836624 8630220025 9316308617 0759676499 9301356594 3705117009 0259876564 4108976170 5530925845 8157993807 9646113013 8229887785 2890604213 5200559795 1272660005 9790594180 8852758766 2226861536 4566625906 1158700573 7782586823 4047106051 5204334014 3591864667 2296353973 2725143715 3818147662 0160073910 9186072599 2482394838 3569847911 9636469441 9154800126 4603259259 5047317126 7995912464 6761906901 1283041616 7926844320 3447823835 8464581316 7124324100 4701372308 6627080120

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 ≡ 26 (mod 63)
• Q(1) is not a perfect square: it is ≡ 13 (mod 64)
• Q(2) is not a perfect square: it is ≡ 34 (mod 63)
• Q(3) is not a perfect square: it is ≡ 5 (mod 64)
• Q(4) is not a perfect square: it is ≡ 42 (mod 63)
• Q(5) is not a perfect square: it is ≡ 61 (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 = 37 4670231288 4486392544 0573743050 8979732812 3071727531 2334481059 6379232239 3959839754 1265955645 7231550778 5200172564 1256536802 5564741918 8562388312 2284162192 3647989197 8089887758 0889450234 2018303703 6498776563 1482236876 8422569098 1045103760 1004579664 7422531035 3816472285 5692471152 0052705224 3215141272 8270633974 7744640810 6539084903 5827946376 3705154816 4524707251 6411719225 3742645901 8831875344 0449583088 6428481959 7375646996 6837526290 3302502571 6972345853 2568679604 6555924117 3458069819 3606920799 4086121820 3730061880 8675020300 3318364767 3575711109 1262080513 8957236515 0239102754 6890558842 0207517710 2710745862 8962623273 0533153495 7725558114 7023086449 0964380173 5707555408 9442130187 3585945323 9452005854 0901947395 9924147069 3311667954 4834601359 0137859940 9214649669 2693836586 8008717201 6505176061 4184313061 6126725865 0933258610 0358555747 7360124404 5538787763 2288294337 2794108809 0811814771 2097148623 9009130838 4347938855 1964988544 7216292371 3365673974 2327167274 1586420128 2564914535 7369677142 1244242382 9130107003 5501695649 6245468883 5579429200.

With those constraints, the unique continued fraction is: {0, 2, 2, 1, 1, 2, 1, 1, 22, 3, 2, 5, 1, 17, 1, 1, 11, 3, 2, 1, 2, 1, 2, 3, 1, 2, 4, 4, 1, 1, 1, 6, 5, 1, 5, 1, 23, 884, 1, 17, 2, 1, 1, 3, 36, 1, 1, 1, 26, 1, 16, 3, 1, 2, 1, 3, 1, 2, 2, 1, 2, 4, 1, 4, 2, 1, 1, 8, 42, 1, 4, 9, 2, 8, 24, 4, 1, 2, 4, 1, 3, 1, 5, 34, 2, 1, 1, 1, 7, 11, 1, 35, 11, 2, 2, 1, 25, 1, 1, 1, 2, 3, 31, 1, 1, 3, 9, 1, 2, 2, 2, 3, 1, 1, 1, 600, 1, 1, 2, 1, 2, 15, 5, 4, 43, 4, 7, 2, 1, 86, 2, 13, 7, 1, 3, 1, 3, 1, 9, 1, 57, 1, 1, 1, 1, 1, 1, 2, 1, 3, 4, 35, 1, 1, 1, 1, 9, 1, 21, 2, 1, 3, 1, 2, 2, 25, 1, 1, 8, 2, 19, 5, 1, 6, 17, 1, 1, 3, 3, 34, 1, 9, 1, 2, 2, 1, 3, 6, 7, 1, 39, 1, 13, 2, 3, 2, 8, 106, 2, 9, 1, 3, 1, 1, 1, 3, 3, 2, 1, 2, 1, 7, 1, 1, 2, 4, 2, 2, 11, 2, 1, 1, 1, 5, 1, 307, 1, 1, 1, 5, 1, 21, 1, 1, 8, 3, 1, 2, 2, 19, 4, 2, 1, 9, 9, 31, 1, 1, 1, 304, 2, 1, 4, 1, 7, 2, 1, 9, 1, 1, 3, 5, 2, 8, 1, 1, 3, 5, 2, 3, 1, 2, 3, 1, 1, 7, 19, 63, 1, 3, 12, 3, 13, 5, 1, 2, 1, 11, 2, 1, 2, 1, 17, 2, 3, 1, 5, 2, 1, 1, 1, 1, 1, 220, 1, 4, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 2, 4, 4, 1, 2, 1, 8, 1, 1, 1, 4, 1, 1, 4, 1, 2, 1, 1, 3, 8, 1, 3, 23, 6, 1, 1, 8, 2, 7, 2, 10, 1, 1, 5, 4, 1, 1, 1, 11, 1, 1, 8, 33, 4, 1, 1, 1, 1, 27, 2, 37, 1, 14, 1, 17, 1, 4, 7, 5, 1, 4, 1, 1, 1, 2, 1, 1, 2, 1, 3, 1, 87, 1, 3, 3, 1, 13, 1, 7, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 11, 1, 4, 8, 1, 1, 1, 2, 1, 6, 12, 3, 3, 9, 4, 4, 25, 4, 4, 1, 1, 1, 3, 2, 13, 3, 1, 2, 2, 3, 1, 1, 1, 10, 46, 3, 1, 16, 1, 4, 1, 1, 2, 3, 1, 17, 2, 1, 1, 1, 1, 6, 1, 1, 5, 4, 1, 3, 1, 1, 4, 2, 1, 1, 2, 3, 3, 2, 90, 24, 11, 4, 3, 4, 1, 4, 9, 2, 1, 6, 3, 27, 14, 3, 1, 6, 2, 18, 2, 1, 1, 3, 2, 3, 1, 12, 39, 2, 2, 1, 10, 1, 2, 1, 2, 1, 14, 14, 7, 1, 2, 1, 19, 1, 3, 43, 2, 2, 3, 3, 3, 4, 20, 1, 14, 2, 2, 19, 1, 2, 4, 30, 1, 16, 1, 1, 10, 7, 25, 1, 5, 1, 23, 5, 2, 2, 1, 4, 1, 2, 6, 3, 1, 2, 6, 4, 134, 1, 1, 1, 52, 25, 1, 11, 1, 1, 2, 1, 1, 11, 1, 1, 3, 4, 2, 4, 1, 3, 2, 4, 1, 13, 1, 8, 3, 1, 1, 1, 6, 1, 1, 1, 8, 15, 1, 1, 3, 26, 1, 11, 3, 1, 2, 34, 10, 5, 3, 1, 1, 2, 5, 25, 3, 15, 2, 2, 1, 1, 2, 1, 1, 3, 25, 9, 1, 1, 2, 1, 37, 1, 2, 2, 4, 2, 47, 2, 3, 2, 28, 1, 2, 2, 1, 2, 1, 1, 35, 2, 8, 1, 5, 2, 7, 5, 1, 1, 4, 3, 1, 1, 2, 2, 53, 1, 1, 2, 2, 8, 1, 1, 3, 3, 2, 1, 6, 2, 2, 2, 16, 1, 1, 1, 34, 10, 1, 24, 2, 4, 2, 3, 2, 3, 8, 1, 2, 3, 1, 1, 3, 12, 1, 5, 52, 1, 6, 2, 55, 2, 1, 51, 4, 1, 2, 17, 6, 1, 1, 1, 10, 10, 1, 1, 28, 1, 3, 110, 1, 3, 2, 1, 2, 18, 12, 3, 4, 1, 6, 4, 3, 27, 6, 1, 1, 2, 7, 1, 79, 2, 2, 176, 1, 90, 4, 2, 8, 1, 3, 12, 1, 1, 1, 25, 13, 1, 2, 26, 1, 5, 1, 13, 2, 4, 226, 4, 6, 1, 2, 9, 1, 4, 25, 1, 4, 1, 5, 3, 8, 1, 3, 51, 1, 5, 12, 3, 8, 1, 1, 1, 2, 2, 4, 6, 7, 6, 1, 4, 146, 4, 1, 1, 10, 5, 7, 28, 1, 2, 2, 156, 3, 3, 4, 2, 3, 3, 6, 1, 4, 1, 18, 1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 8, 93, 4, 1, 2, 1, 8, 1, 10, 1, 1, 4, 18, 38, 1, 1, 1, 2, 18, 3, 2, 2, 2, 1, 28, 13, 4, 13, 2, 3, 2, 1, 6, 2, 2, 9, 1, 6, 2, 1, 2, 1, 4, 1, 1, 5, 1, 1, 4, 2, 1, 3, 11, 3, 75, 1, 13, 1, 3, 7, 2, 1, 1, 1, 7, 4, 1, 24, 1, 1, 1, 1, 3, 4, 5, 3, 3, 1, 120, 2, 1, 3, 1, 4, 1, 1, 3, 4, 1, 6, 3, 2, 10, 1, 2, 1, 23, 2, 5, 71, 9, 1, 7, 1, 3, 1, 1, 1, 17, 2, 2, 4, 4, 3, 1, 2, 11, 1, 1, 1, 2, 1, 7, 2, 40, 3, 1, 2, 1, 1, 3, 1, 4, 1, 2, 52, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 6, 17, 2, 13, 1, 2, 4, 72, 2, 2, 3, 3, 7, 1, 1, 3, 1, 5, 1, 9, 3, 10, 1, 2, 1, 16, 28, 1, 5, 24, 1, 1, 4, 4, 1, 21, 3, 1, 1, 1, 19, 1, 1, 1, 12, 1, 81, 2, 2, 2, 1, 1, 6, 1, 392, 1, 10, 33, 2, 1, 2, 1, 24, 1, 2, 1, 3, 4, 1, 1, 4, 1, 1, 2, 2, 2, 1, 1, 1, 103, 2, 10, 5, 8, 1, 2, 4, 1, 4, 1, 1, 4, 9, 2, 60, 1, 3, 1, 1, 1, 1, 4, 7, 1, 1, 1, 1, 1, 1, 1, 3, 126, 1, 5, 1, 1, 14, 1, 7, 3, 2, 6, 1, 1, 1, 5, 4, 1, 1, 1, 8, 18, 1, 4, 1, 1, 7, 2, 1, 3, 7, 1, 1, 25, 1, 4, 1, 3, 4, 1, 1, 1, 4, 4, 2, 1, 3, 1, 1, 4, 2, 2, 1, 5, 2, 3, 90, 1, 7, 5, 11, 1, 3, 1, 1, 4, 1, 2, 1, 12, 1, 2, 2, 1, 12, 1, 1, 2, 23, 1, 12, 1, 2, 1, 14, 1, 1, 2, 6, 3, 1, 2, 26, 3, 2, 4, 2, 3, 1, 31, 2, 1, 1, 3, 1, 2, 7, 3, 1, 2, 3, 1, 2, 5, 25, 2, 1, 319, 2, 1, 9, 1, 5, 1, 2, 8, 1, 5, 1, 35, 1, 2, 3, 7, 1, 1, 2, 67, 1, 7, 5, 5, 2, 2, 3, 19, 1, 65, 6, 4, 2, 1, 112, 18, 1, 2, 2, 9, 6, 5, 2, 4, 1, 1, 1, 4, 32, 11, 3, 2, 10, 1, 5, 2, 4210, 1, 2, 1, 6, 1, 6, 3, 3, 2, 1, 1, 7, 1, 8, 1, 6, 1, 12, 2, 1, 22, 7, 10, 2, 1, 2, 7, 2, 3, 10, 4, 1, 1, 1, 1, 3, 3, 2, 7, 2, 2, 1, 3, 238, 2, 3, 6, 1, 14, 3, 1, 6, 1, 2, 1, 44, 1, 12, 12, 1, 1, 1, 2, 4, 1, 6, 1, 1, 2, 30, 4, 5, 2, 1, 2, 1, 4, 1, 38, 1, 4, 2, 2, 2, 1, 1, 4, 1, 7, 1, 9, 1, 3, 1, 5, 2, 3, 4, 1, 23, 1, 1, 2, 6, 2, 5, 5, 1, 25, 1, 1, 1, 1, 3, 1, 3, 4, 32, 4, 6, 1, 3, 2, 2, 1, 4, 1, 3, 1, 4, 2, 1, 1, 1, 3, 2, 665, 5, 3, 2, 36, 2, 2, 2, 1, 4, 1, 3, 2, 1, 2, 16, 1, 1, 3, 1, 3, 1, 21, 7, 1, 1, 35, 3, 1, 3, 1, 2, 1, 1, 1, 10, 1, 9, 1, 2, 1, 4, 3, 1, 13, 12, 1, 1, 25, 1, 2, 1, 3, 4, 2, 4, 1, 15, 1, 1, 1, 3, 1, 2, 9, 1, 2, 1, 1, 158, 2, 4, 5, 3, 2, 1, 17, 7, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 17, 19, 1, 1, 1, 14, 17, 2, 1, 23, 5, 7, 2, 1, 58, 3, 3, 1, 2, 1, 9, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 8, 20, 1, 1, 1, 2, 73, 15, 2, 1, 3, 1, 11, 2, 4, 1, 15, 3, 59, 25, 5, 1, 2, 4, 2, 1, 35, 3, 7, 1, 3, 1, 2, 13, 7, 4, 1, 4, 2, 1, 6, 2, 2, 3, 1, 1, 1, 10, 1, 95, 4, 2, 2, 5, 4, 1, 1, 1, 2, 1, 1, 5, 2, 1, 1, 3, 1, 3, 1, 1, 1, 4, 2, 1, 2, 1, 1, 2, 1, 1, 5, 4, 1, 69, 1, 3, 1, 1, 1, 8, 5, 9, 2, 1, 2, 1, 2, 3, 1, 5, 3, 2, 1, 1, 1, 10, 66, 20, 2, 4, 1, 2, 2, 1, 2, 1, 14, 2, 1, 1, 7, 58, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 4, 1, 4, 2, 1, 2, 1, 42, 1, 7, 4, 1, 19, 1, 4, 5, 52, 4, 1, 1, 1, 1, 1, 1, 12, 1, 2, 8, 12, 1, 7, 1, 5, 1, 1, 5, 1, 1, 3, 4, 1, 5, 68, 1, 1, 21, 1, 2, 1, 1, 61, 1, 8, 1, 2, 3, 1, 3, 3, 43, 1, 1, 1, 15, 1, 12, 15, 3, 1, 1, 1, 25, 1, 1, 16, 1, 2, 2, 1, 1, 15, 13, 1, 2, 1, 1, 1, 1, 1, 3, 1, 11, 1, 1, 1, 3, 2, 2, 13, 1, 11, 5, 1, 7, 1, 1, 5, 3, 3, 1, 2, 5, 18, 1, 51, 1, 1, 1, 3, 2, 50, 5, 1, 1, 1, 2, 1, 7, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 2, 2, 5, 10, 1, 163, 1, 2, 1, 2, 1, 3, 6, 2, 79, 1, 1, 5, 2, 1, 2, 3, 2, 5, 3, 2, 1, 14, 2, 1, 1, 1, 1, 8, 1, 71, 1, 1, 1, 1, 3, 1, 13, 3, 1, 2, 6, 1, 3, 8, 1, 5, 2, 3, 1, 2, 1, 3, 2, 3, 3, 1, 12, 2, 1, 4, 1, 4, 1, 1, 3, 12, 1, 1, 1, 1, 4, 2, 4, 1, 4, 2, 2, 4, 1, 5, 1, 6, 88, 1, 2, 17, 2, 8, 2, 13, 1, 11, 1, 1, 2, 1, 14, 2, 2, 1, 6, 2, 2, 3, 1, 3, 1, 2, 2, 1, 2, 2, 9, 2, 5, 1, 11, 4, 2, 1, 12, 8, 2, 2, 1, 1, 1}, giving these values for u and v:

• u= 9 1817434432 6019993263 4928825401 2022459806 8238731813 0743213155 5789574925 8972715705 5945221974 8267255750 7781793430 1101866780 9777234325 1416712303 5137792409 0935768207 7566865562 8118359161 4417531578 5327077597 4664584823 3187399356 5259113949 9630539366 0605442904 1872796654 7276325145 1794565324 2701994950 6557035979 3532335115 7560003401 9355894209 0366102673 8226001693 9127851908 6307412379 7994728076 6908442168 1008309200 8013735857 8823675946 9634932051 4052926947 2164598121 7128703512 7397546730 7300741702 8153881942 0759695129 5430595703 0851754189 2570800687 7443933353 3245447150 9034073144 7384272211 4288708504 1200528136 2644774206 8042780201 7575507650 5840906362 3958693618 2511225655 3608585509 6996847589 0765435283 6387135865 6016952461 4148421289 8431784451 1261296488 5796099530 3663697647 4792028593 4351656908 4791060010 4497654787 2372070712 8712995219 5853716265 2309047674 1599049374 4145286391 7939000014 8232322590 4362153985 3669452929 7398398843 6235067216 8138728622 8294096439 7963597567 1638898692 0582854865 3270216817 5341322235 6641157712 3557673193 8515416287
• v= 21 9181279313 1355645316 4300926204 2399660157 5814114060 8308015859 0187285473 4998446603 9792595535 0465697231 2468697534 7691737048 2363617394 4471511786 0155455881 0423930996 9789107658 1017447855 0034285711 6012745659 3925590310 9796118536 0258245402 6854220411 8501257941 1059308568 3752020129 2626115073 1721308256 9688219030 5788500725 4661586291 6055243521 7380839977 9588068720 8391964761 1968499655 2432004495 9091495873 9327187419 1663422458 8097777175 5670256429 8089876253 6756112924 5220314377 2526009737 0581087913 9768164409 3886451597 3525930128 1188283460 8500661597 6918676237 2354496408 8638093876 2135726853 0265245240 8146290522 1786071465 1350588548 9847948253 3798300880 2931725368 9776669702 6843521282 2818347809 2484394705 4264178258 4782533788 4499717024 8268140312 8085525801 1399074992 9921085395 1904279370 3544975823 4902241605 1668715746 7547147336 9837884587 8418914748 4342412215 6313427709 5554528537 8941403150 6582744011 6491053128 0047947891 3068029501 9558958266 1961367558 5778010592 5575432686 1288171922 3835079480 7596774092 0462293890 7209826606 2333386932 6080433570

… as taking one more term in the continued fraction would give a value of v of 123 4265247468 4959356886 9827741791 8990623858 0754283831 2005499426 3463932550 8352035470 4384392696 5041972204 6026752584 1783584994 4957820683 3067744809 2796448665 9077913686 1296574730 1985887066 7528762413 1778050421 8555964569 8683399349 8126360769 6274952754 7379430925 5354641896 7470461767 5734965516 8074597324 7479444093 5636533824 7973871621 1937286898 9948880721 4927196627 5302683518 8611235253 3125318356 1208359402 6189824267 2244092290 8009056365 0117525314 4576385420 4239077134 5278615976 4554003005 6637728955 5149605579 6727799056 4885240900 0556925075 5792912920 7966350220 9548936912 7310750285 6195450436 9095649567 2162402415 2127499502 5290028906 8693337464 3489228738 8214723895 4605802142 9251803149 5346645362 9797103584 3180716088 6303012458 0692164980 3989958148 0728052367 9702578808 2950607634 3872110840 6873023600 1889103945 7491400364 3754471545 0892074871 9121495537 0708768744 7259800309 4598686278 7906104140 8646263088 3603894152 5314044775 3703088589 9060582567 0884767037 0223491997 1825872584 1819863468 2797298384 2109158525 3448635439 3566984756 0043607607 3032886357, which is too large.

We also need to calculate d = floor(c₄·v/F + 0.5) = 16 4600840672 8811358103 7362931580 2046773449 9915430907 2756307361 7710657530 1842489672 2018595810 6512524649 0570921843 0289956164 2429651170 7398520362 0882575457 6870783549 7004040052 6888819228 0311196201 2747682431 2128993133 3067130942 8919199336 8397727919 4640417892 8724259904 7931769014 1103663639 5021094262 0984627239 2478829176 2472429017 4486836827 1267020051 0604529082 0073956800 6691467700 4627929437 9311445523 5686886655 9912036952 6275014937 4202376402 7820488569 0874581454 3335572507 3278223953 9536132418 2766579413 5757546984 7520611583 2905128115 8548458122 4201381254 7449969648 4666113853 1963468119 8831054731 0946563431 7225060407 2973667929 1819034892 6681768146 8600975550 8375198843 5300401208 8963128358 6829533121 1367745932 1559490548 7664745225 8020989668 3421930815 0614191769 7653754557 7700280345 2717802469 0835659234 3921135836 1244066591 6323467872 0232078559 3758443698 6299443539 9771223070 3326174856 0753856400 4201669157 6312963065 9214540069 9280252189 6183216035 6576064500 9943569237 9685047799 9365611483 2212967672 8572874375 8854333274 8602467989 4492675889 4023570889 2616226882 5814806595 7275682360 8394412505 6795827065 9183366953 4700142147 8323410140 9862939448 3227823119 7861022416 2069068936 2940750642 1743058395 8382838598 1332450575 1315435459 0458265492 7408631126 1874220100 8610142419 0973078984 2894493737 6371396561 4178682342 6659854207 7454036603 6421104839 0161372649 0298354694 4271164249 3274983941 1916894438 1204548308 6234466953 9241589386 0447169594 8179318373 2088235592 0095807832 2346656971 8519758741 6412041231 6464359779 8690869341 2320303916 1327473109 6275103254 8047424891 8220588366 3005176016 6504498209 3727248817 2809375742 3769656980 1147707850 3698831487 5493506441 8611084636 5342627870 2051690098 5383678848 7090326689 9006443099 4942916083 9913836801 8846816673 7454245306 3038168499 8558466290 0410410141 8977419468 1136086620 0909753807 0897361292 2121073652 7914473577 4740765736 2583549873 8832950601 3689309255 2455322462 3643070393 0529348389 7189726589 4773608437 4144027694 1853922565 8723483095 2972402106 4999194349 1175762040 8528837667 4627409286 2289856228 2267728846 2905635112 4933088393 9986642608 7473091697

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₁= +21 9181279313 1355645316 4300926204 2399660157 5814114060 8308015859 0187285473 4998446603 9792595535 0465697231 2468697534 7691737048 2363617394 4471511786 0155455881 0423930996 9789107658 1017447855 0034285711 6012745659 3925590310 9796118536 0258245402 6854220411 8501257941 1059308568 3752020129 2626115073 1721308256 9688219030 5788500725 4661586291 6055243521 7380839977 9588068720 8391964761 1968499655 2432004495 9091495873 9327187419 1663422458 8097777175 5670256429 8089876253 6756112924 5220314377 2526009737 0581087913 9768164409 3886451597 3525930128 1188283460 8500661597 6918676237 2354496408 8638093876 2135726853 0265245240 8146290522 1786071465 1350588548 9847948253 3798300880 2931725368 9776669702 6843521282 2818347809 2484394705 4264178258 4782533788 4499717024 8268140312 8085525801 1399074992 9921085395 1904279370 3544975823 4902241605 1668715746 7547147336 9837884587 8418914748 4342412215 6313427709 5554528537 8941403150 6582744011 6491053128 0047947891 3068029501 9558958266 1961367558 5778010592 5575432686 1288171922 3835079480 7596774092 0462293890 7209826606 2333386932 6080433570
• z₂= -8 0802294951 1642208684 0607340549 5410085827 9148975313 8434119947 1651336563 0568790104 5754391154 6983486536 5038063923 8423109617 5291888025 4087515629 9411171389 2988462782 4712660067 7645047593 5305731118 5882705841 4274871294 0116479447 6171594425 3965231216 6339380349 8353887937 1198841882 6727470141 7250743762 1554908027 5449092380 0891829398 7471689478 1672172854 5417513656 8748293602 9845881843 7024455272 4426007307 3136868680 1729221506 8090449442 1626332775 7770986663 7254618903 2133836929 2809255010 6034916591 4127950250 8722200701 4484935510 4317507670 2464098444 1678126992 2954685195 7459398812 6042957551 0088505932 4302546599 4159573289 6939243136 1821954110 4911565519 7073994185 6220836777 5848252860 5084908441 2652621389 5772716292 6104763693 3033090333 5745140136 2328393182 9948753065 1137398867 6276597970 6281499209 9838836182 7632100757 2388538144 6556460952 6045817963 6111045994 3318350153 8080165594 0007470477 9249422320 0347688285 6225623364 1622887907 6008937683 5805924932 1591523684 6729592087 0806593835 3784838672 9099239836 7615392885 7822503133 0830890199 4242007746 9896125377 2946396860 3857755600 0665224407 9403586678 0484744715 4373952505 8408979247 6731625514 7755061780 7566572610 2171797466 8414687431 3626971651 0461894728 4195031379 0286508352 5781245635 9615732955 4080453654 2477276378 7335251869 5450938492 5965358208 0549089679 8314287751 1013669383 3292853158 9616287649 1250350605 5918334623 6384846296 6098043402 9506718638 7515096723 7274298252 9368089122 4822033398 3266021206 0550641584 6881541769 1149885453 4684439646 0457772230 9104136376 9810778147 9956941717 0813813187 9497346925 8076087730 3915162267 6629832162 0203386837 2485926050 9830739875 1145227540 5809485380 5394838368 4797964937 4701530208 5719219710 9325359438 3946918428 5642566746 7103572082 4621494929 9314513979 1050048834 8512877908 3937660565 5476925677 4834574289 8945024103 4561266418 5470579849 4539968460 5276456966 2627623375 2310410925 8058096601 7838558091 6420794569 1162019339 2057455116 6791676824 5294041313 9764882121 7999355987 4213153833 6085728486 7583167357 1401749385 5895732098 4599700312 3723752843 0423632227 3657667640 5512473623 9775668590 1743132456 4208477710
• z₃= +132 0704887650 8753275923 8186455042 9140562269 4657901432 7755769664 9902887658 1149236180 3733068357 5416333101 3854954346 1021644519 4856821463 4059677571 7582888680 9736373680 0224036003 0089602021 7686274136 0608290088 4917977281 3455692929 0857001176 3296683906 6346506584 2269980736 5384910246 2789631990 0980874752 4696907239 2162475768 8407515161 0437318661 3723172579 9578858227 3125561138 8200356466 9602420818 9613175841 5574407043 4519024560 6714603397 2918890980 2345607081 9058949673 7120492668 0432452481 6809939466 9635975114 3427031680 6671280251 5602721849 9815188571 0348937733 8678052430 2230854625 8872895883 3068729758 3793415748 0417301308 8313838216 1442169450 2239413548 1465783492 9398332593 3914120408 4149136800 7227442608 8056251598 9952902759 1346463305 8836075369 6814867033 6106131408 7717541623 2262097864 0762144302 5596422847 4892564814 7586788914 9040023039 7330075805 7092667530 3313181490 9179559006 6428170254 7736525797 5771245486 2419367631 3181844242 4146301160 6656494710 3550393736 2695269778 4084272863 3141479817 2757358906 4062344002 4016701172 2624007583 3449823361 8591442166 1548043482 4629343620 7930444727 4813048620 4330267249 0179987695 8788684804 4072410229 5023936096 9498656105 3648114665 0502608631 6271309242 6306106709 6953988524 9529137366 5454153458 2017130461 7304340557 9569782126 4695072165 2408054630 9292569997 7246347468 9211300241 8285365216 5466505162 1164451876 2835482014 0478148117 9261217214 3218862344 8389582390 9757256803 7982129188 7468437238 8140261266 9458571417 2822795921 5586345324 2813919556 7972360414 9014381612 4598237030 7991633076 3807186920 1422314874 5790231659 1769415969 3017478608 4152413275 7088072382 4419580337 3700649410 0836133781 6000588791 1037351486 5602784192 6061062209 3126282910 9688264901 9644917986 5021421280 1529038606 7443974147 3581045327 8055426063 7619930470 7017831867 7980152215 6227903054 8387592621 7842760453 0298369734 1067856280 3538797657 2586494186 8244118396 8904017677 4752944517 8449708703 5791408873 0077701069 0501123114 5936232403 6786302216 6239416174 1245239924 6303820301 4751803765 5547850293 7744845817 5793682104 2681997526 9590202617 5000365631 8489236357 3704380958 9547673847 0884656353 5007752274 4572689129 6752256566 5278856151 2869954192 8565904745 9766788597 6453760223 1960123504 7603980833 5135359795 0779536945 9967896653 3838870432 5677990535 7231097823 1492255557 8091928795 9928928531 4027853264 1279782573 2663623014 3495841151 3886931575 4561144540 0419608513 8203180044 8330081933 0461333595 4699421119 3487641517 1061338830 1271253505 4961868032 8872517609 1828010551 0855795833 0390011194 3245538281 6045301863 5595615832 3045197443 4908790644 2224417340 7861244720 8655932282 3866532451 0095941320 2176511049 4922039163 3796414903 0237293286 7746790444 4809317415 6203727862 2617299229 5764571200 6838769298 6674309219 4762787270 6791131152 5917374533 6274763802 3585785790 8284665809 1699699747 6008078157 7444752506 4378712137 4386128116 3196641781 0255444727 6794663585 6927259743 7947041755 4342511156 8138131335 2436440249 8702641817 4726292696 5836038740 7586076360 3492363447 4120306350 4203770037 9387216220 9975041053 4652251829 1259021161 2683298616 0371951552 9159089645 8844384274 8748026799 9804259157 6608827631 1314965272 6270903708 6532066916 2169015949 6841409187
• z₄= -16 4600840672 8811358103 7362931580 2046773449 9915430907 2756307361 7710657530 1842489672 2018595810 6512524649 0570921843 0289956164 2429651170 7398520362 0882575457 6870783549 7004040052 6888819228 0311196201 2747682431 2128993133 3067130942 8919199336 8397727919 4640417892 8724259904 7931769014 1103663639 5021094262 0984627239 2478829176 2472429017 4486836827 1267020051 0604529082 0073956800 6691467700 4627929437 9311445523 5686886655 9912036952 6275014937 4202376402 7820488569 0874581454 3335572507 3278223953 9536132418 2766579413 5757546984 7520611583 2905128115 8548458122 4201381254 7449969648 4666113853 1963468119 8831054731 0946563431 7225060407 2973667929 1819034892 6681768146 8600975550 8375198843 5300401208 8963128358 6829533121 1367745932 1559490548 7664745225 8020989668 3421930815 0614191769 7653754557 7700280345 2717802469 0835659234 3921135836 1244066591 6323467872 0232078559 3758443698 6299443539 9771223070 3326174856 0753856400 4201669157 6312963065 9214540069 9280252189 6183216035 6576064500 9943569237 9685047799 9365611483 2212967672 8572874375 8854333274 8602467989 4492675889 4023570889 2616226882 5814806595 7275682360 8394412505 6795827065 9183366953 4700142147 8323410140 9862939448 3227823119 7861022416 2069068936 2940750642 1743058395 8382838598 1332450575 1315435459 0458265492 7408631126 1874220100 8610142419 0973078984 2894493737 6371396561 4178682342 6659854207 7454036603 6421104839 0161372649 0298354694 4271164249 3274983941 1916894438 1204548308 6234466953 9241589386 0447169594 8179318373 2088235592 0095807832 2346656971 8519758741 6412041231 6464359779 8690869341 2320303916 1327473109 6275103254 8047424891 8220588366 3005176016 6504498209 3727248817 2809375742 3769656980 1147707850 3698831487 5493506441 8611084636 5342627870 2051690098 5383678848 7090326689 9006443099 4942916083 9913836801 8846816673 7454245306 3038168499 8558466290 0410410141 8977419468 1136086620 0909753807 0897361292 2121073652 7914473577 4740765736 2583549873 8832950601 3689309255 2455322462 3643070393 0529348389 7189726589 4773608437 4144027694 1853922565 8723483095 2972402106 4999194349 1175762040 8528837667 4627409286 2289856228 2267728846 2905635112 4933088393 9986642608 7473091697

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.

P has a single real root at:

• 0+ε∈(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.