Primality Certificate for (2302^2521-1)/2301

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

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 3 suffices.

Express N in base F

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₁= 1095 2761707101 0265704298 0366341824 0313863288 1476858632 1316203593 7207679078 7187218566 1635423741 6366101329 2715690182 8788839793 7814160871 1209870592 7003235530 0338149934 7943713147 3037881608 2537648536 0402806274 1222770565 9788099518 3701596616 7945129273 9535746325 5734830121 7221734116 5541855439 3209469782 3770155847 3980956748 4732139594 3958519929 8836650442 7858401849 5529065323 8016748487 3648424591 8201296765 2958795270 9207498651 5390965260 1433808324 5502279873 3130596985 8921762884 9223060168 6153760661 4489424854 1856004924 2018344424 4433071063 6013493693 6480140317 4240325603 5951859977 8525927709 1698477939 0474182575 4639254787 1243599022 7149275071 3921319493 9221195528 0594285940 7914366230 6155153661 8968825171 7974869507 2256785905 2930126303 8268695877 3142281643 0906736095 9258204663 8045602997 3603362467 6380594812 7329826333 6013727868 2332454431 8570688277 5161269808 9853035238 5187208831 1431891325 2825121948 9874494803 4609123566 2430295542 5257743729 3902873735 0755492950 4425720192 6885461009 2716861359 7928668618 8957722949 7561309156 2490585650 0641917985 6738086636 6904198149 2714419588 3933920766 8385129423 6934577244 9585907454 4598503241 4504524196 9910908247 0042706419 5152209956 0592857226 8984081953 7017988786 3361184194 4158339595 7149374011 8654259028 1668805171 8682112796 2748848096 1004041496 7071710605 7090994931 7520244631 1413938651 7443786795 8787818943 1850871802 9188104998 2237698885 2924108073 2315131131 9229461810 1675636466 7503376494 9906262125 8661747128 0161705697 7353829760 4311085629 7166230707 3370177302 3985018239 9643569165 3858108185 4947417000 1306040400 1195912316 8042147379 1444022621 9056483523 0971604885 2068713558 9972487448 3604217759 1971418402 0213924219 9088243841 4235177695 6396926246 7199405774 8616079555 8821188577 5222657100 0540910809 1303315083 5963282122 0090610200 7209724361 9774636658 2581874869 3793173369 8113227569 0832412825 3725960278 9490949436 2477692976 4628359905 4679036223 3881463937 2512534076 3980141875 4280976253 9484662894 5190288163 5790943371 0428048766 6247073785 2205795416 0901179516 1054627011 8964886854 0510741537 5834550055 4764872195 8470195051 5235088448 7987332917 9273190725 0035816581 0349299991 6577080304 4755932160 6760032817 0241602900 6879034202 9964071837 8640757565 6059992977 8354794411 6327663074 5835778906 9764217067 2038054544 9364813130 3892937134 5465622260 1772001524 8440886539 4352074385 0266039734 1850710336 3593285713 4840034593 2738188972 6897387989 7973773198 5229257676 8535490401 7377707665 9732111395 8708562391 5161356330 0134545052 3734758744 9307469241 3869446277 7336110032 3151612790 4065047728 0390212198 0250157571 5566132787 8487567597 6377992235 3327675243 3681163863 2516144301 6646784311 1450222094 2176240909 2248028927 8582105454 8754305134 9483390429 4184610584 9503134608 8973340297 7323938337 2365448192 1624360149 2739301361 0255883741 6310966391 4239470208 2828201475 0996184331
• c₂= 1023 9214308791 7734589569 5745506890 8472006904 1743177421 0360604600 2628936407 8773581631 6820495767 0396886842 5142520814 1209581193 8764478528 5066584943 4859831618 3143821899 0803797977 5218414331 6444645637 8089710142 0398577809 2310942079 3933504449 7713109908 1811405910 9095988073 2872002967 8599528147 3466161959 3998868941 5827444935 2907945416 9718578457 1549565596 7184905106 5166134667 0792250878 8037785780 9900051822 2317180222 3036171393 5833665345 1748876704 7830922714 0880520679 5886840273 5714615666 1487078357 2081980350 7256131377 7495438646 5575398335 7615615376 4856245306 3053537392 8384766439 8923786307 6509088553 4435684345 1583763286 9163318952 7457289186 8085162530 8028649991 4331200624 6434125302 9872676100 6060725871 3976708411 8680960322 1830267405 0526178115 3605490738 8620570858 9964309989 3787687822 6109967626 6110960055 7752033857 9057784101 6394317702 9013192903 4687940760 4327952039 9192502462 1484224025 0361055907 9132904441 5282303260 7461648090 6833380488 7333090818 5482564769 5595289147 9695720748 0210503269 1337376656 3819728457 2907900471 4547357319 4749222937 4512120692 0819808210 1415522817 9897018599 0182186438 1756544601 8767288853 1540161126 5320237095 8200647343 5983298197 8276280396 9494351244 0481608689 2121396111 3952730361 1121083047 5927526051 5117622696 1365602332 1976012781 4158038780 1770239511 1770722203 9299993102 6831537196 5078766370 4189595467 3954721171 0563082597 3046911598 1962612751 6029951520 1326936204 9512436400 6954807220 5843412531 8046136087 6984916113 0519275976 9615744074 6573499426 9783878554 8335580534 8070462966 3196476388 2576640540 7852702227 9226681980 3772431324 2927750697 1899923898 5660927547 2748503013 0834798342 6806325504 9628819818 1173957521 2604254133 4894873823 3833548049 2106702584 6087348165 6485655704 5392380802 9118821067 7084678597 3121484552 1797640388 9750089146 9104784986 1956334867 3757266968 2133065582 4436913450 1110888622 7878243127 1533168672 8303006943 8824919694 7694914178 5610227509 5355725730 1843664450 2938429928 5641231301 1263503566 0983826164 0766368368 4975233246 5484595160 0922894699 4822210659 7286997660 3757567727 9861474741 6274589600 0097037143 2661103790 6232568834 6229105170 2517445024 8616151758 9785863218 0892879480 8531779220 9640367657 0433589717 6192735153 6263259256 8607111534 9531432502 9909645125 9568910761 2277308515 4934959284 5612603655 5084942610 2436999528 4125313264 1726628883 9801886847 9745808482 3612959602 1438776974 8662880514 1323035551 7932167221 2570956310 3668664218 6946783644 2787676289 8615541645 8901822149 2572481530 9381288677 3280496548 8204632410 3915849935 4597337649 4883657797 9470516309 1998339794 2361508748 3374157784 0813835983 9555269628 7561185916 1293315157 7530003133 6118938442 1530109673 0449721419 9906224387 8173690035 4301345854 2908113497 0133994135 5341222905 2224623756 3589322223 0616534613 5640457348 7209575950 6015996788 2477691514 0923817572 0982539648 3095817199
• c₃= 224 1283860897 4770452522 3852940546 2354157954 9271447387 3778944397 2009560855 8841830947 3892558742 2760969932 4917014003 1648703006 6605425100 2363265796 2952223477 5919249427 1091326359 1417441227 4682376221 6480025805 9800986389 5673332076 0981456989 1936750048 8246502300 3010783469 8679700086 7921619577 3911968321 4996147679 8559595622 1075056019 6055883429 5872345460 5491639702 8360707096
• c₄= 543912 4705549109 2530743067 2191222502 9162058218 6927031769 0548968697 3679484414 1142584127 6028850641 8278488007 4217440975 8635565821 5148395032 2257765865 0080045544 4154595203 1011774799 1125735916 9739714181 3541980190 2209888314 5096184689 3565866992 3606000240 3067609170 3513245620 0999855098 3324175768 1327609793 3882967354 3352717754 2974338603 0114974671 7563249310 1975188601 9133759202 8047452076 7482861372 7148079486 7785787199 4165976618 9406140234 4475662867 6126344190 1009341066 5027604684 4463348077 3064329086 6458627630 0647727496 6845771875 0945806863 7580016345 1619977343 9555533462 7225522943 8444357802 6108770955 0622373315 7500070598 8182097921 5328681277 6284442878 8770390085 4030875390 4952189133 2596824034 2584915482 8615064465 2093341290 2947890450 3735878502 5017408376 7301221938 9400421047 7093009723 1646241097 3037635276 1749730165 6664688639 4921206606 3705553187 4696211416 8087078328 1144428824 3204628302 4791642189 1402561008 5946350191 4715708029 6751268768 8282207579 2217181842 2258840539 4368279093 6798316235 0259908387 1452633108 1757373144 8849962730 9079079019 4113428126 6937239274 6455016033 3781777375 9498547555 2536106396 0294475029 1619545047 1247392379 1592868693 3795982300 5552953897 0012360703 2093093043 1196492022 1595191920 5896175664 1548669511 4645523259 6269100146 7832222460 4515603952 2689971862 6543470976 7173837006 5088406485 3452399549 7144133384 0396983247 1360521547 2990820938 7134526662 6547090793 0461304685 3983198597 3487613204 3297553590 0679089726 5196606983 7179813459 6754682473 7089566681 3816446751 7460054807 4519970524 0861329738 1440254762 7877236585 6057537850 4688251200 7256997983 1747933376 3705624796 2186062428 2130947038 3529429264 7992945228 9236474487 8579186602 7941549681 3439156484 4172680388 9410526860 3806219363 8548306476 9506540840 8155550781 6360082140 5304857550 8837816729 7826422459 6545308096 6268500623 9851996221 1855453809 9627052332 6705335521 5195705183 9614273595 4615876430 1376627979 1240941426 6218124791 7828813959 3921159229 2462502732 9958687075 4517819487 9037858709 3308783109 0889385717 2949735059 2818409884 0587563156 0144532536 7944453809 8486270666 6577280994 0704996812 3389351394 2335279146 5743992169 4254611989 3898286663 5150947162 2814748836 5367173238 5170823413 2528515568 0251947430 7265174548 8113090902 4043728058 4230746072 9643461292 4989449361 7698997752 0134495800 7927110416 1535006827 6007563173 4795188289 3114588165 7361924926 7628823899 2590193403 1951371297 7445723264 6017014650 6311937840 4996976196 4741157190 4123966783 7822175875 2697288529 4121386485 6042129073 5501739628 6154403368 7758598329 8834905411 8041631324 6739438192 4958973795 3249591827 0441571814 8419909558 2753162481 6951516736 0206976700 1222751156 4536826782 2049135806 0001398286 0930445342 8676685401 3154107592 3839918922 2468786916 9796074319 6941249040 0453089181 3469251858 4284146163 6171064553 1336805249 2092037360 2565951412 6621485842 4923593781 2822452803 0948679171 5160942844 5216268319 4194260789 8114412823 8544456303 6016572250 9381228722 7607903807 9681051600 4289973685 1853281010 4940367460 2930472617 9867274433 6429814547 4253303878 4202503181 6144048510 7282138355 9711307637 1406110588 0154247269 2321092072 8337260854 4014747408 6654112642 2426060139 2354767351 6302397700 1782196317 5235698529 9857042850 4659077599

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

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 = 3 2905435593 4186080758 0653292535 8527401211 0756871044 3957256523 1085502474 3086200903 3202582938 2508695305 8633176495 1952381116 1235508123 4375735251 3602129542 9559663341 7347072274 7903517102 1831672922 8673652372 2061193453 0525641456 9977441927 2907982183 4639995171 3208996192 1783426965 8664368008 7385032511 4714756188 1130089901 0527147928 5643911334 7915560149 7069275068 5655205403 5582371434 9836520857 4988278012 9947613439 7084072840 8862847396 7792614589 6248412068 2049956407 6676154528 2915083737 9082427899 7961879225 4748445233 7661731390 3107214840 5973546840 7980809705 7393885548 2105267788 9608346479 7336982173 7567598505 8862616294 9634026515 8020802512 1780588929 5009556221 1413652955 6092122758 5761494861 1388316541 8160239222 9287602867 8657954588 8651748513 5470787572 9956432019 0594767816 0507074970 9817177067 5858739932 7521552871 7550245562 4662501532 1134705471 0642791170 6962314942 7102527974 0030980762 6397299261 6304369695 1628645568 6494587259 4970155133 6178288130 2833740675 8599546510 4831967556 0584863881 3172066691 3739041477 5008685317 2783505087 4191246221 8442008746 0590179258 5240655486 4112366393 1726236307 8972734166 1434408789 4224253514 6315464166 2726435157 2824659899 6533548354 2023706720 5277921111 2402629573 3719172313.

With those constraints, the unique continued fraction is: {0, 2, 4, 1, 1, 1, 2, 1, 305, 1, 2, 1, 10, 2, 1, 1, 1, 2, 2, 12, 2, 2, 4, 6, 2, 1, 12, 1, 14, 1, 1, 3, 2, 2, 1, 6, 1, 1, 2, 3, 3, 34, 2, 1, 1, 1, 1, 3, 1, 3, 5, 177, 1, 1, 1, 1, 3, 2, 1, 17, 1, 2, 10, 1, 1, 10, 5, 6, 2, 5, 17, 1, 1, 6, 2, 2, 2, 8, 1, 1, 1, 19, 41, 1, 1, 1, 1, 19, 3, 1, 3, 7, 1, 1, 2, 1, 9, 1, 2, 14, 3, 1, 1, 5, 2, 2, 11, 1, 131, 5, 4, 4, 1, 5, 3, 5, 2, 1, 1, 1, 3, 1, 4, 4, 4, 5, 3, 1, 1, 1, 1, 6, 1, 4, 1, 9, 1, 12, 1, 24, 1, 5, 1, 1, 1, 16, 3, 1, 1, 1, 6, 1, 5, 2, 1, 1, 1, 8, 1, 4, 3, 4, 1, 1, 1, 1, 2, 7, 1, 7, 1, 2, 1, 1, 26, 1, 30, 1, 9, 3, 1, 5, 3, 2, 1, 7, 2, 1, 2, 17, 1, 2, 1, 1, 6, 1, 1, 1, 26, 1, 16, 1, 1, 5, 6, 5, 16, 1, 4, 1, 1, 35, 4, 3, 3, 1, 1, 1, 5, 3, 9, 1, 1, 2, 1, 1, 4, 385, 5, 1, 2, 53, 17, 1, 1, 1, 1, 1, 1, 7, 1, 1, 3, 3, 3, 1, 1, 1, 6, 1, 1, 1, 1, 2, 10, 8, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 1, 1, 1, 3, 9, 22, 1, 2, 5, 1, 18, 80, 5, 2, 4, 4, 109, 1, 6, 10, 3, 47, 2, 1, 1, 7, 1, 2, 1, 2, 3, 3, 26, 3, 11, 1, 3, 1, 4, 1, 1, 3, 468, 3, 1, 47, 1, 1, 8, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 1, 3, 2, 84, 2, 1, 1, 1, 2, 7, 6, 3, 1, 1, 1, 2, 1, 2, 3, 2, 9, 2, 3, 1, 144, 2, 1, 2, 4, 3, 6, 2, 1, 14, 1, 1, 3, 1, 1, 1, 8, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 5, 9, 1, 2, 2, 1, 6, 1, 15, 9, 3, 1, 2, 1, 2, 1, 1, 7, 4, 2, 1, 8, 5, 1, 1, 1, 7, 2, 1, 21, 1, 2, 2, 5, 4, 1, 1, 5, 1, 7, 1, 2, 1, 2, 1, 1, 9, 17, 1, 1, 1, 2, 1, 16, 1, 4, 50, 10, 1, 1, 1, 3, 2, 1, 1, 1, 2, 4, 1, 2, 1, 1, 2, 16, 712, 1, 1, 3, 1, 4, 2, 14, 1, 1, 32, 2, 14, 2, 3, 1, 2, 1, 14, 3, 5, 1, 103, 14, 1, 1, 2, 1, 4, 29, 1, 2, 2, 1, 6, 14, 1, 6, 1, 4, 6, 1, 14, 1, 2, 2, 8, 1, 4, 2, 13, 1, 10, 1, 2, 101, 4, 1, 5, 1, 2, 16, 1, 13, 2, 1, 1, 3, 2, 11, 2, 47, 5, 1, 20, 3, 1, 245, 1, 11, 1, 1, 1, 3, 2, 3, 16, 2, 1, 3, 1, 1, 2, 1, 1, 6, 2, 1, 6, 1, 34, 1, 10, 1, 1, 4, 3, 2, 1, 2, 16, 5, 1, 5, 1, 8, 1, 3, 4, 70, 2, 1, 2, 1, 2, 2, 4, 1, 1, 1, 1, 1, 4, 2, 2, 49, 25, 1, 38, 1, 3, 1, 1, 3, 3, 1, 1, 2, 1, 1, 2, 3, 2, 12, 1, 6, 1, 3, 1, 17, 13, 6, 1, 1, 1, 6, 2, 5, 1, 1, 1, 1, 2, 25, 1, 9, 1, 30, 4, 1, 16, 1, 2, 1, 5, 2, 4, 1, 2, 3, 1, 7, 1, 6, 2, 17, 2, 16, 1, 10, 9, 2, 5, 30, 4, 1, 35, 15, 4, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 3, 6, 2, 15, 4, 2, 3, 11, 2, 1, 2, 1, 56, 2, 1, 3, 1, 2, 3, 9, 48, 1, 9, 1, 1, 2, 58, 1, 7, 1, 1, 2, 3, 104, 14, 4, 1, 1, 1, 27, 1, 4, 4, 2, 1, 5, 1, 2, 3, 1, 4, 4, 4, 2, 24, 1, 2, 2, 1, 2, 1, 13, 1, 3, 3, 2, 122, 1, 2, 1, 3, 8, 1, 142, 3, 2, 2, 1, 3, 1, 2, 4, 1, 10, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 3, 1, 18, 7, 1, 5, 15, 1, 2, 1, 1, 1, 2, 4, 55, 5, 1, 31, 1, 18, 2, 8, 59, 1, 1, 1, 49, 1, 2, 1, 5, 32, 2, 1, 46, 1, 10, 194, 21, 309, 2, 11, 1, 12, 13, 1, 4, 61, 69, 2, 1, 1, 4, 1, 19, 13, 3, 1, 1, 6, 1, 23, 1, 2, 1, 1, 3, 1, 3, 5, 1, 4, 2, 1, 3, 4, 1, 1, 1, 1, 1, 5, 2, 2, 1, 1, 3, 1, 1, 1, 4, 3, 2, 1, 12, 2, 2, 118, 11, 1, 2, 3, 1, 2, 8, 2, 1, 1, 3, 2, 2, 3, 23, 1, 1, 1, 1, 1, 3, 2, 1, 174, 1, 13, 3, 1, 26, 1, 1, 4, 1, 1, 1, 8, 4, 1, 4, 1, 4, 1, 19, 2, 71, 1, 29, 17, 2, 50, 1, 9, 1, 1, 30, 1, 2, 1, 4, 1, 4, 23, 1, 1, 6, 1, 3, 1, 9, 55, 2, 1, 4, 1, 1, 1, 1, 4, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 3, 1, 8, 8, 6, 13, 7, 27, 3, 1, 3, 2, 42, 3, 4, 3, 1, 4, 2, 2, 3, 7, 1, 1, 1, 1, 5, 2, 3, 1, 2, 1, 22, 1, 2, 80, 3, 1, 8, 2, 35, 2, 1, 1, 1, 1, 1, 1, 12, 1, 1, 1, 1, 1, 2, 2, 3, 8, 3, 1, 1, 65, 28, 1, 2, 2, 34, 15, 7, 2, 46, 7, 4, 1, 1, 12, 14, 6, 1, 4, 1, 4, 1, 44, 1, 1, 1, 116, 11, 27, 1, 2, 1, 1, 11, 2, 4, 1, 1, 5, 5, 2, 3, 1, 1, 2, 2, 4, 28, 1, 30, 10, 4, 3, 1, 7, 2, 3, 1, 10, 5, 1, 2, 1, 11, 7, 3, 1, 9, 1, 49, 1, 4, 3, 2, 1, 7, 1, 1, 1, 6, 1, 2, 3, 3, 3, 2, 5, 2, 1, 1, 1, 13, 1, 1, 2, 3, 4, 1, 1, 2, 1, 3, 2, 3, 2, 1, 3, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 15, 1, 1, 1, 1, 5, 1, 1, 5, 3, 1, 3, 1, 3, 21, 1, 17, 1, 5, 4, 1, 1, 1, 1, 7, 5, 3, 18, 1, 3, 1, 2, 1, 1, 4, 2, 1, 3, 3, 11, 8, 3, 2, 2, 4, 3, 1, 2, 3, 12, 1, 26, 2, 1, 6, 1, 2, 2, 4, 1, 52, 1, 1, 10, 28, 1, 1, 1, 38, 86, 8, 1, 1, 404, 2, 2, 1, 5, 2, 1, 2, 7, 451, 7, 4, 28, 1, 1, 8, 2, 8, 2, 1, 2, 1, 1, 1, 4, 1, 37, 1, 162, 2, 1, 1, 8, 75, 3, 1, 12, 2, 7, 1, 28, 11, 1, 56, 25, 1, 2, 1, 3, 1, 1, 1, 243, 1, 7, 2, 2, 2, 1, 2, 4, 1, 1, 2, 1, 1, 1, 2, 1, 4, 2, 4, 1, 1, 13, 2, 4, 9, 2, 21, 31, 1, 2, 1, 1, 3, 2, 6, 3, 3, 2, 1, 31, 1, 4, 2, 3, 1, 1, 3, 2, 1, 2, 6, 2, 2, 1, 1, 4, 7, 3, 22, 1, 15, 1, 3, 2, 2, 2, 2, 1, 1, 1, 1, 2, 1, 5, 2, 1, 5, 3, 4, 161, 1, 1, 15, 1, 1, 1, 4, 1, 1, 1, 7, 2, 49, 1, 25, 1, 1, 1, 1, 1, 77, 1, 2, 2, 1, 1, 1, 14, 1, 4, 3, 1, 1, 3, 4, 1, 1, 3, 4, 1, 5, 14, 4, 1, 4, 4, 1, 1, 53, 4, 1, 1, 5, 1, 118, 4, 19, 1, 3, 1, 7, 1, 1, 1, 3, 1, 1, 1, 1, 41, 2, 5, 6, 3, 1, 1, 2, 3, 6, 2, 8, 1, 3, 3, 1, 1, 8, 4, 1, 2, 2, 1, 8, 2, 3, 1, 1, 44, 1, 3, 2, 1, 1, 3, 2, 6, 1, 1, 1, 4, 16, 79, 1, 1, 1, 3, 2, 1, 2, 1, 2, 4, 6, 2, 6, 1, 17, 2, 12, 4, 1, 1, 1, 4, 1, 9, 2, 3, 1, 1, 1, 1, 3, 1, 5, 2, 7, 1, 4, 5, 1, 1, 2, 1, 14, 6, 1, 1, 1, 6, 1, 1, 5, 1, 3, 4, 2, 2, 1, 4, 6, 7, 2, 2, 1, 1, 16, 1, 1, 1, 3, 3, 4, 2, 1, 3, 1, 14, 5, 3, 4, 1, 3, 2, 1, 4, 6, 2, 2, 1, 1, 15, 1, 1, 5, 11, 4, 1, 1, 1, 1, 2, 1, 1, 15, 2, 2, 1, 5, 1, 6, 15, 3, 4, 249, 5, 1, 1, 1, 1, 2, 1, 9, 1, 1, 2, 25, 2, 3, 3, 3, 2, 1, 1, 1, 18, 2, 1, 35, 4, 2, 5, 1, 3, 1, 6, 1, 2, 1, 2, 6, 4, 3, 4, 3, 44, 1, 3, 2, 1, 13, 2, 4, 1, 24, 3, 1, 3, 1, 1, 2, 3, 1, 2, 96, 1, 3, 7, 1, 14, 1, 4, 1, 1, 1, 3, 1, 1, 3, 28, 1, 17, 6, 18, 1, 5, 12, 5, 5, 5, 1, 1, 1, 1, 5, 2, 2, 8, 2, 92, 3, 6, 6, 1, 3, 5, 1, 5, 1, 8, 1, 4, 1, 11, 1, 2, 1, 4, 4, 5, 1, 1, 1, 4, 1, 4, 56, 2, 1, 4, 1, 1, 1, 4, 3, 3, 1, 118, 2, 8, 1, 8, 2, 1, 3, 20, 1, 5, 3, 2, 12, 1, 4, 1, 2, 2, 2, 5, 1, 4, 15, 1, 3, 4, 1, 10, 2, 2, 2, 3, 2, 7, 3, 4, 5, 2, 19, 2, 5, 32, 3, 2, 3, 3, 5, 1, 5, 2, 3, 7, 2, 1, 1, 48, 1, 1, 1, 2, 2, 5, 3, 1, 8, 1, 1, 24, 59, 12, 1, 1, 1, 3, 18, 1, 1, 3, 5, 1, 2, 3, 4, 1, 7, 3, 6, 1, 163, 1, 1, 53, 1, 6, 7, 2, 18, 1, 2, 1, 1, 1, 25, 1, 14, 11, 1, 3, 1, 13, 23, 5, 9, 1, 23, 1, 2, 12, 4, 1, 7, 1, 1, 1, 7, 1, 2, 1, 1, 1, 1, 1, 3, 3, 2, 1, 2, 1, 3, 1, 2, 2, 2, 642, 1, 1, 9, 10, 2, 5, 97, 3, 1, 1, 3, 1, 1, 12, 2, 9, 2, 4, 1, 5, 3, 2, 1, 4, 2, 2, 20, 2, 41, 5, 3, 1, 1, 2, 1, 3, 6, 22, 1, 1, 3, 15, 1, 5, 1, 1, 1, 1, 1, 4, 1, 1, 3, 2, 1, 1, 4, 10, 1, 1, 4, 1, 54, 3, 1, 2, 2, 6, 1, 41, 15, 21, 1, 2, 1, 1, 7, 1, 58, 1, 1, 1, 5, 1, 1, 3, 2, 2, 20, 1, 2, 3, 6, 17, 3, 147, 1, 1, 6, 1, 33, 1, 17, 20, 4, 1, 1, 2, 6, 2, 2, 5, 2, 1, 1, 1, 9, 1, 4, 4, 2, 13, 9, 1, 2, 9, 1, 3, 1, 2, 11, 1, 13, 1, 5, 3, 2, 2, 1, 6, 4, 17, 3, 1, 5, 5, 1, 1, 2, 1, 1, 11, 1, 3, 8, 1, 4, 2, 1, 10, 1, 9, 1, 1, 2, 3, 11, 1, 1, 5, 13, 7, 1, 4, 10, 1, 4, 3, 2, 1, 3, 1, 1, 1, 11, 3, 1, 4, 1, 1, 3, 1, 1, 6, 14, 2, 2, 1, 14, 1, 14, 1, 2, 3, 17, 1, 1, 3, 12, 1, 1, 1, 1, 18, 2, 5, 1, 25, 2, 1, 6, 1, 14, 1, 6, 9, 1, 6, 1, 3, 1, 10, 1, 252, 1, 34, 5, 2, 2, 3, 1, 1, 1, 2, 1, 1, 17, 2, 1, 19, 5, 22, 9, 3, 1, 6, 2, 4, 5, 4, 12, 9, 1, 3, 90, 1, 16, 1, 3, 40, 1, 5, 3, 5, 1, 1, 2, 2, 4, 1, 3, 1, 1, 7, 3, 2, 3, 5, 2, 1, 1, 2, 3, 2, 1, 3, 1, 2, 1, 1, 2, 6, 1, 1, 4, 1, 6, 9, 2, 13, 2, 2, 1, 1, 1, 1, 1, 2, 166, 84, 2, 1, 1, 3, 1, 3, 1, 1, 2, 2, 5, 7, 3, 1, 6, 11, 11, 2, 2, 2, 2, 18, 1, 14, 4, 4, 9, 1, 8, 3, 2, 3, 1, 4, 1, 14, 1, 1, 2, 2, 1, 6, 2, 2, 6, 2, 7, 1, 1, 1, 1, 23, 1, 2, 1, 47, 12, 1, 1, 1, 8, 5, 2, 1, 8, 4, 5, 1, 1, 2, 12, 1, 15, 1, 1, 1, 1, 1, 9, 1, 1, 3, 1, 4, 1, 2, 1, 1, 17, 5, 9, 5, 1, 6, 1, 26, 1, 1, 1, 4, 7, 1, 1}, giving these values for u and v:

• u=6974156242 4510610521 2467722772 1592064494 4258164078 5132257548 4431455493 5182864634 2565691519 4410499541 6789075334 5200474167 7226787717 2865319115 5697446960 5711989769 7960523198 8319557488 3173457350 4585791914 1620977826 7322905389 6734491127 1838447283 7078214980 3666054788 6235183658 5201164683 7694598874 4124631511 0342475955 0412192315 4609814894 8122314567 8924725237 0982564567 9906582056 4946764246 8598941217 3807882467 6225855207 8929324516 0000714952 9825676950 3508442236 7706435046 9736836472 4287710980 6524988572 3540148857 8628473160 7825902200 1721942733 6531348979 9117884374 1613907300 3337945501 1895209982 8814430978 7943162407 0159085598 0656565520 6399811081 1582004009 5259413446 6500511400 2287119496 3775396355 0987747412 6284374898 9076667017 7316917148 5423486993 5618694838 2057610930 4446535201 5135083436 0004838469 5713058100 2886154939 9232254272 3637942497 5978015167 1434212971 1789597055 2281820380 2494438634 0295708337 8156737550 7854758126 6202247632 9715746404 1888223339 9832148185 7133871415 6970281344 2322571003 8300903483 1029615301 7248354345 9901839028 5707552458 6097979125 8526075153 6263798689 8488423635 6015123990 7447185710 2753937902 8049446386 7751942369 5943604786 0311209546 2701060464 3519550948 7247447438 1396728159
• v= 1 5452551011 7886896185 5037769915 0973045830 1388555783 8292322094 9931501234 5745433765 4785083081 1898875219 0371903650 7748081337 8428787385 2195576197 8177213085 3119127504 8230318544 2347782429 5978823756 7275356024 8622959821 6335267224 4654871054 2165149600 6726781979 0614864920 8864646551 2209596042 5605307195 3487140767 6180198453 3155009983 4445344900 0932527865 2134494005 8145806986 7912455488 0641272658 6579641566 4684176773 4799136674 8438954264 4540128390 4158548354 5731354009 5755869739 0902709703 5714437110 9033088868 7897999434 1115809384 1277858805 8502315621 4989348885 0168783063 1632010586 9351108205 7616960282 2284673662 1290956813 9948482760 0644042178 8445245867 0374379961 8092965812 2690766193 2712965267 6144847585 1430695544 9085595655 9844202566 0663526857 3672275687 4808781861 4247872397 5492259880 1168174595 8535564026 4248271562 9459379456 1949336489 3293727553 4447040515 8827563481 2347721433 9300096713 8543830925 3793144317 8152554626 8125907053 7835068530 0731501914 2870843228 8892165358 6047201055 9402424478 5770610082 7927164146 9490730144 7542012837 5584449693 6627972421 4354254142 1957700641 0341373162 9451766437 6789982370 0403810541 2838213438 3782239933 1270260252 7630533424 2565721929 4103559044 5944868601 5076774308 0793910376

We also need to calculate d = floor(c₄·v/F + 0.5) = 346 3355319241 6969596276 1202000662 5019118849 3612421468 7394416773 5849493030 4787786099 2033108738 4654202096 0379419678 4525036503 9617598287 5868934516 0109958443 8951607229 0375773865 8178675803 3976444506 7383398178 8710031126 6155507714 0076890016 2865688771 4879152603 6921062246 7535542554 1938443046 9179010861 4195324677 2876437039 8193860903 9216916355 0260700938 6362431204 8008206969 2653073441 7052345234 8249624415 7282998794 8724302344 8562884677 7885380079 5542191953 6744076746 5516462501 8808483793 6147643539 4620850521 6119858629 2341988015 6825553690 5889641014 1272956192 9429266477 9722594860 3618273236 0090587534 8559566271 8547132786 8196246983 1492350569 8523579421 9235501198 9687318775 7894184297 1149728692 2562023187 5233379392 3764139880 5031885831 9422758584 2498176191 1729268451 6705864667 3474148207 1752048521 8252708537 6051117141 3211448192 0693493152 6885096687 3254384632 4451289933 3505331819 6660556582 5077444646 6142427509 5282136802 7510146805 5842791971 3958312833 2093678158 2867544298 4772693964 3743565405 6697655300 1078830802 5433286853 1822758438 6084772468 2533409915 9530661986 0519142765 1612193967 6334744103 2906938129 5764607685 7926384599 1122627894 5277792031 1176779550 3089596291 7916346975 8468717319 8412853155 6758762631 8119319392 3861742572 0254220298 0339247902 2672999578 3474935048 4828400809 5050292091 2202413764 7681272667 9956367874 6939489517 0115360235 3654594683 7923146433 0849284512 9482283948 8726734727 4877159676 4294052312 1471629384 2100719257 5612803436 2295412043 8875423624 2071997867 7862511365 3225663730 5896236310 4795199446 9307629560 4383402197 1197332051 5864526679 5606514193 7992198621

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 5452551011 7886896185 5037769915 0973045830 1388555783 8292322094 9931501234 5745433765 4785083081 1898875219 0371903650 7748081337 8428787385 2195576197 8177213085 3119127504 8230318544 2347782429 5978823756 7275356024 8622959821 6335267224 4654871054 2165149600 6726781979 0614864920 8864646551 2209596042 5605307195 3487140767 6180198453 3155009983 4445344900 0932527865 2134494005 8145806986 7912455488 0641272658 6579641566 4684176773 4799136674 8438954264 4540128390 4158548354 5731354009 5755869739 0902709703 5714437110 9033088868 7897999434 1115809384 1277858805 8502315621 4989348885 0168783063 1632010586 9351108205 7616960282 2284673662 1290956813 9948482760 0644042178 8445245867 0374379961 8092965812 2690766193 2712965267 6144847585 1430695544 9085595655 9844202566 0663526857 3672275687 4808781861 4247872397 5492259880 1168174595 8535564026 4248271562 9459379456 1949336489 3293727553 4447040515 8827563481 2347721433 9300096713 8543830925 3793144317 8152554626 8125907053 7835068530 0731501914 2870843228 8892165358 6047201055 9402424478 5770610082 7927164146 9490730144 7542012837 5584449693 6627972421 4354254142 1957700641 0341373162 9451766437 6789982370 0403810541 2838213438 3782239933 1270260252 7630533424 2565721929 4103559044 5944868601 5076774308 0793910376
• z₂= -506 6772821969 8196856757 3102088165 2346944120 4882998835 5455328757 1175002640 5871468859 3514143434 7574081766 1090006385 4210000249 4733785646 8881127394 6195344867 1491108884 3784141079 4392187503 8225653463 0654920608 9405068455 6367855910 7356327416 6764134247 0213452360 1520984149 2269764944 6891120470 8968273528 9794283290 5496150203 2669275991 8127044004 9209292270 2824186874 4130845939 9456188468 6893520838 5799770609 2510601229 2077893417 1638518647 3640223952 2372662498 4881185530 5366250020 7402743202 8725162041 9645615705 9398237067 1508137262 2839735581 3366224062 2438731552 1756606199 2783692326 0936301895 3360230778 1315502250 3070641987 9277690130 0729303307 4337982225 3841184350 7456547617 8463535152 8714507189 9736403064 9615124711 9535264669 6444684573 4231678469 6292713139 8993219981 6381014005 7049354822 7482935270 6866829299 9721815948 9991471540 0006526606 4990148243 9531612450 2153727054 0909327271 6090456588 5717158701 4281202444 1843395885 7916590937 1677963768 8699505468 6170958928 6016115392 8010856260 9356442298 5408712233 1517321359 4782998053 1928062474 5525898603 2801146091 9967674209 6567417111 9705610484 7177553989 6308207899 5829834250 6733041863 5316841141 9776559836 8346731650 5715330994 3177358841 8137180915 5065028922 6783506830 2701201420 9464253510 8894780986 3932893670 7206173046 2593659725 6143715595 0456972752 9744679143 4934182198 7522759889 4191598186 1494874721 1218065054 5391108992 3971776662 1576770727 4657203258 7194229818 4939531438 8993029223 7558303012 4807213846 8855382733 4536490179 4703662288 6743677340 5898178268 1975764021 3363725530 5400519569 4244775822 7163995455 0635247904 0700281075 9303923106
• z₃= +930 9813009453 3353982050 2645231684 8726363084 3417478166 0165496773 2428226360 6031901131 5541390450 8419441790 5465972661 3031142139 6467337071 3851626011 9611498029 4365793302 5354485659 1427526133 5493465830 6776320254 8574984541 3248018106 8535736507 3314116824 5752873377 9683256671 8784755676 2972262232 7468152303 7522590710 4339743831 2514618741 0737941462 4365883733 4620071025 5669312353 8126502251 7054765222 8969245140 1815593866 5248660807 7486122496 9072525936 0472527836 1587567711 3841081790 0387996463 4731804356 2758069292 3949228341 2696656891 5596729813 8174240885 5044364983 4566599810 0009136400 6001309920 9062684852 3775265514 6876794297 3678247451 4435890197 3557152000 2129447279 1992328956 1934428371 4597662964 7264875836 1753085057 9197610194 5687164762 2394100645 2059553309 6163196143 0387596950 5018973826 4686344168 9351154966 9991573147 8247746450 5912945019 3065065729 6084273332 9870717204 2058379391 5564756736 1341591837 9532838710 1151514983 1632087683 1633759628 5899897155 8986336615 9984997579 3895614176 5655078406 2513508160 3372315920 9998275444 7429825762 0063818543 0284467718 4641135723 1811228697 1435235783 6203346367 4336260860 6827931849 3443574070 2205805870 8786032948 2299020324 5708598070 2990100435 0469699044 4188967237 4115487481 4178594078 1447122412 7121987839 9839004338 4720361059 1307532373 2156982457 4964242219 4743965222 7991846448 6016643564 9517213568 1272234558 3877407781 9391710096 4226868060 9687842225 5386122535 8426727798 5915693831 2534214729 0106156136 1851972828 3891692341 2954684982 9607173987 3445506704 3685920821 6777949759 1398311761 8319014127 1313053062 5606552002 2644103702 4945705285 7956171330 3836173431 8702911531 9964843991 5386912412 0184353043 1316000918 6795113124 1012392668 0554768828 2000933290 4526709195 2791302367 9787728638 5223491554 8230262170 7361249069 2643668084 3785822087 1138404790 3696407840 8515688008 3790349742 8754249972 8494785688 6935048568 8160731146 2560482859 2486417352 9970786519 0707587587 2281235614 6780245875 7265857873 0125295852 3270845587 1224496812 6789511088 8815300154 8143155148 6270493662 6704177887 8177767775 3108600233 2980868754 4516998316 0327513594 9962247010 7554627615 3973405259 6877117754 3026466058 1198236591 4213918663 7670863493 1586646859 4905883374 0303337379 1033020069 8990588151 4187872211 0810022272 6211496337 8917387363 5372346274 3607700283 0266350054 5820204098 9017870172 3704393159 4530393052 1390216851 3278618337 5972244079 5693004217 7306546617 4371202707 7777437480 0152052258 1135432289 4798163196 0125591242 1104844765 6457830458 2406727904 4986868728 4085834431 3380007299 7240333531 5021056986 8590118103 9349327619 9080120279 2590972207 0462601912 0960792245 9779824867 7838543878 6413525211 2964652632 1655110029 3268544634 6253131188 9311180158 1757533325 8846698809 5150907152 8026184530 2276648190 3114314849 6923471443 2452078227 7114902295 5717667567 8346778036 1711121867 2403842188 4552543733
• z₄= -346 3355319241 6969596276 1202000662 5019118849 3612421468 7394416773 5849493030 4787786099 2033108738 4654202096 0379419678 4525036503 9617598287 5868934516 0109958443 8951607229 0375773865 8178675803 3976444506 7383398178 8710031126 6155507714 0076890016 2865688771 4879152603 6921062246 7535542554 1938443046 9179010861 4195324677 2876437039 8193860903 9216916355 0260700938 6362431204 8008206969 2653073441 7052345234 8249624415 7282998794 8724302344 8562884677 7885380079 5542191953 6744076746 5516462501 8808483793 6147643539 4620850521 6119858629 2341988015 6825553690 5889641014 1272956192 9429266477 9722594860 3618273236 0090587534 8559566271 8547132786 8196246983 1492350569 8523579421 9235501198 9687318775 7894184297 1149728692 2562023187 5233379392 3764139880 5031885831 9422758584 2498176191 1729268451 6705864667 3474148207 1752048521 8252708537 6051117141 3211448192 0693493152 6885096687 3254384632 4451289933 3505331819 6660556582 5077444646 6142427509 5282136802 7510146805 5842791971 3958312833 2093678158 2867544298 4772693964 3743565405 6697655300 1078830802 5433286853 1822758438 6084772468 2533409915 9530661986 0519142765 1612193967 6334744103 2906938129 5764607685 7926384599 1122627894 5277792031 1176779550 3089596291 7916346975 8468717319 8412853155 6758762631 8119319392 3861742572 0254220298 0339247902 2672999578 3474935048 4828400809 5050292091 2202413764 7681272667 9956367874 6939489517 0115360235 3654594683 7923146433 0849284512 9482283948 8726734727 4877159676 4294052312 1471629384 2100719257 5612803436 2295412043 8875423624 2071997867 7862511365 3225663730 5896236310 4795199446 9307629560 4383402197 1197332051 5864526679 5606514193 7992198621

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.