Primality Certificate for (6311^2593-1)/6310

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

We need the product F of all the prime factors from this partial factorization:

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

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

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

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F⁴>N, N can have no more than three prime factors.

Express N in base F

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

• c₁= 2 5307574156 8842233006 4924435063 7951584943 1184173119 6232081346 2246932390 2176440514 8526535394 4980137017 7517002531 1466212634 4252263006 0922434419 1686482168 3936179375 4713869340 1211358956 7647253578 4368674393 3221537516 4253738005 7817298259 8048509345 3727690802 1220497066 4391750331 5067327436 8467161340 4611351405 0083694062 1987523805 4520255962 2549409308 5001810620 8117811364 4585430608 3845441538 9372625545 7072360539 2509931279 3572736883 7613451458 4665206913 6300752567 4397735442 3805284602 4836728893 4639327405 8448940911 8285068302 6001696214 8645781376 9639363203 6210455073 2504961879 7878801277 4144517155 2248289701 7896567531 7162598527 1423066049 8181654301 7692134915 3947295613 9952046471 4650835612 4272729201 4714056151 4048364716 6751140256 6743243971 9260037810 0506635875 2222809528 2269538652 6760297472 3516743706 6643484637 0100654836 4426743776 0464137315 6337013463 4018928307 1206094259 8348608013 5086248500 0066695236 3260039413 2309875929 0979689215 4257798232 7308545249 4342354517 3323314679 4894932297 6164449294 8161717994 1564423434 6253905454 3124080624 6775696697 4107288372 8785911418 8816321754 2486335473 8324971606 9076200711 0080709859 1665836260 4703630035 2124968167 1016351503 3086236019 0933765382 5657163916 6320439243 0259380345 8445355455 0342238929 5588977428 6580770985 0965897837 5349466211 4951600003 7744343507 0221664554 9246132911 1589187001 4319284189 5423846061 6150708385 2728769582 0088378137 7488055979 3684175073 3986926809 0908207470 4487358055 3481167893 0208176529 9907878683 9267516252 6428885152 7303369817 1924358696 9943302451 2898315334 2655603527 2646412936 5150350363 2465071683 6247521774 0327879781 4264325709 4770727548 1139919782 4622788642 6833260073 6415120658 1042312756 7049522992 8948844643 9525222120 6009458366 1002524878 5289425103 9204761973 7822294313 1333354269 5859667032 0568068174 0897195708 4972961171 6098109119 9090773588 0702385738 9505635461 2240269795 4583333970 1746785523 3552317710 5107716008 8698545291 3512421939 4790663297 2229290426 5023468815 9443138837 8464179678 8168135826 4243679004 5292338715 2526962547 0705353005 8213466647 7214448159 4406181507 9814526723 6328645577 6645768732 7285419178 8413061127 5967165137 4016439205 2200731487 9834123736 3929484639 4082874970 7174819068 6685883457 8955749221 8679755101 5496580434 5385614548 6740334433 1609377532 2909711419 5188455656 6370359444 6662306062 2112264372 6665386574 3893768939 5410384705 9489658271 8350758801 4734867850 6119151589 2500365661 6665706280 1778561888 6339391918 9061829097 2613915909 3811682468 0223676100 6433728854 5330700696 9760482347 6141979607 5753988248 8159543747 5786472990 5298137382 5451445698 5755940263 7039563685 5395831093 5612543231 1724300428 4732459430 6245805873 0891902229 5905192365 1176470765 9926414443 3135757032 9331278750 3029057115 2455950341 1133725413 3436664614 5567835584 0190950715 0169102248 8046111312 5181912317 9916570756 4244420021 4474557246 1271712371 6058165087 2984698377 6754620339 4803077040 9300878599 5323635657 9417657076 8713504076 0805541715 6387174594 3513625733 2902780525 3820285304 3230068254 5346526763 8429228902 6148460901 0974530014 1784505864 6126133416 3741373577 7419626397 0123141529 6694542501 8727555677 3030519738 4275035965 0421978113 5290543741 8420609719 0093274490 9126793502 7909070845 3271103662 3285240025 1063859456 2788817448 7261884961 6092360658 5619265009 4363079125 1113445755 6187662956 9873321059 2214600259 9797515225 4681583356 0241400037 3840764727 6434529938 0293759391 8203845836 8170005989 3207731245 3880169993
• c₂= 7822671241 2214365292 7405236354 0233313168 8874509656 9579645498 1260030992 0327616523 5780223445 7603592116 5581592198 9735815654 3471430902 8063752944 5474103254 1447903504 2151928373 5998893189 2505285981 6329087353 0546764517 2174394509 9632538978 4101614819 3986382357 5812775297 3786359116 5473790177 2849727414 9375902362 9901424733 5168720784 4711202291 3936352810 6398186383 9760395015 4332482885 0623382747 7897818936 0122512747 2830174737 2221996323 8712934620 8597451767 6322987944 7630890623 3676447806 1607912056 6234955522 3435701528 2618840669 9078931292 0654615179 8200241530 7480533703 5819457477 0639118361 8234337737 6770171783 7906052968 0562870465 6589410944 5850139977 6759533062 6722752571 0429928085 3343971197 1840707280 8244737562 7138882846 0369375757 9845323871 7962826509 3426620263 9668441264 9711002388 9195375875 7541574021 8146052302 5851835932 6300346160 2385923081 8186173697 0640808117 6093746121 3615668856 9675049330 2629184990 3718378112 2614480493 0575445799 4019917420 5959776436 9330616123 4798318216 1724823458 1457750850 0629948486 9898093142 7884687045 6592836105 2609307211 6268491507 8336316233 2532480754 6130938194 5870377967 7588969731 1274762484 4352393442 5164421341 2570371959 7965789439 9577071028 5607967527 2558983812 9046921826 9488765920 6784926610 9022107210 4423001973 9331857742 1659663723 2211161806 5805824276 3168802282 4419541091 4488004249 5485464799 1203880206 3771271388 8995637815 0454123902 2018568687 6438750760 9980520804 3190616474 3492961784 2461510546 0233677484 5887567052 1636840861 0978657348 5226476886 5892366662 4833757168 1624397758 7695438323 3509725880 5565843323 0490260753 7189349834 9488932473 9159500089 1410478588 3316078599 4205106577 1821533992 3362254797 2660071123 5471403554 6561746319 7930558313 8032288216 9780698504 5013522233 6522423208 0466974256 7945436850 3882263600 8454853735 5017591237 0037263706 0343914135 9128176394 9208258453 5878952896 1254918030 2695835245 2869655860 5127143612 2310949619 8794235962 1716795490 2989514680 9156718814 8865115144 7215535001 7987682378 0160326300 4549228833 8155898402 9377309600 6786660206 7098078330 4062852632 6083162447 0447257546 4787010383 8706934332 6407145417 9141599792 2832416536 8240566534 3179235581 4662761353 8813791294 1614058177 7204217146 5133863632 7536647243 8722978717 2430920765 7717698057 4114161836 7475592391 3130641488 1435977897 8261907931 0019729486 6708198112 6331546169 6589618351 8759185614 0634792189 2748848950 2356924625 2556106504 2317659160 9809262723 1330781460 2386880836 5703637977 8442130210 0812228027 7399007709 1913810749 2390053204 2517976309 0446562143 9968245981 3405511001 6778736813 6508799686 2498943644 1827020820 2724420389 7504160310 0510882460 2888760052 1394718817 2703986732 9286307495 4014257491 7937299958 3668078111 7414006567 2454421757 8835649489 7062728340 2582532460 0532492868 1171813090 0409942419 9917251077 9123265745 9488835432 9937335367 7142081542 4920347473 4414969256 9086087199 8984756962 3831169617 6819037245 8376777034 0093506182 3115202606 8607303418 1600342417 2977423013 9504227773 5145875818 0301107184 7118772405 6682566625 0522593651 7127432622 9201216035 0863905456 5900791843 8778989694 8856128194 7499860945 9702280692 0450270094 8187191257 4069818854 8229148707 6172018604 2636349231 5086787231 9070548193 4690009287 4001889561 3515367596 9829089722 0020165732 7068249352 1138355005 6074069482 3521614946 0418757769 2695184828 2492791802 1857417031 2568654629 3287156031 3212867802 5486130354 9442522695 9494735365 7004925272 3993499349 6426602933 4469292014 7833228906
• c₃= 377819127 7871716158 2356899165 4812502911
• c₄= 1007024195 5599408081 0594491445 3641019828 1709890970 3459454459 8036671683 9684989716 5304255142 2932371404 5305694636 7976268292 7109330157 9110301578 8375178064 9566142865 3054223336 1753515158 3871721630 7090121643 3676659516 1691736705 7173488267 8721516072 7867397348 6513904040 6180240531 8555988198 4657763816 6893497488 8621954799 2277188640 7817856653 5511279261 4097676422 0337995988 2650202588 8335135771 3820372032 9143687509 7519672400 5437449835 7122201058 5262897984 3813148103 5421336729 0575527936 5493365235 4376716023 3254991359 7088073986 6729056596 0247457062 6532169158 6665579159 5688018465 6340774911 5931767659 5716547473 9571897548 5246367517 3452014870 6109333591 9590197254 2210503144 6156493764 9428821138 5962316313 2370598353 5378273644 9622561630 9383966085 2477386060 2015801776 5711899678 4956115239 5821863842 3361578255 9157208808 8057168113 6115052248 5814291330 9510247461 7338406104 9203779353 7243758565 3503413407 6766749061 6222473371 0827356980 6317331295 4475122021 3917555113 6997374280 5857548627 6869700742 1367429972 2190580565 5050864648 6728598427 4575744439 0849967390 6446192276 9676012435 1348804035 8515435324 1641637435 3086102142 8176193383 6536781446 0017260919 6209184831 3209790953 7318555363 9413947287 2967584426 3324662526 4852747542 3749845118 8592828074 5732216775 8769702444 6895540519 5747627396 1979068792 9635004887 8214528372 0812723587 7367993412 9643001805 6111347391 4252480484 5125831500 3759509837 6632478287 9664231130 7672163307 7647527105 2226901219 4040860429 5688327193 3162723788 2376582051 7814026267 6206997459 9565935005 5924792329 5163300643 9704325081 1707689405 9742554982 3379726358 7352971844 0820974798 0792261683 2701519378 2198715549 1976442588 1508272117 9385079768 5420231856 5083555355 6046544077 6448019989 7654795917 1778976091 4204495448 5755264409 1852313877 9266103503 1694301102 7047990423 0316432878 5626274492 3718492789 5817147945 5284033074 4058891831 8183753197 1301144376 4867990680 1157548522 5723582671 9634342016 6530021029 5183845426 3435639911 1252313241 3719656978 2462667209 3512847856 8538310929 8379870424 2631748867 5939119464 9371222921 5602208205 1265981265 7083132596 3724279690 8511355062 4617808396 2593049945 2403518815 4666791048 2408897333 4232209141 2590185722 2958972900 0568530189 0082347919 9197396392 3681276361 1071139358 5791656717 5296134017 2201382262 9930607172 4694160178 4886656762 5450313389 5434685106 8797131497 4059138058 2986668616 5035091583 9838185699 4186748869 7331896023 2903707776 8300262165 6634483769 8154604828 5601383898 0204097855 2438342520 5236877135 4450206698 2438122252 6435272740 9873971023 1392586886 0132920721 6451807581 7527844119 6004893267 4724396858 6080264440 7813525089 0989683366 8089161738 1961396903 8209149005 1251429853 2907710181 1493770527 8781764709 0710490861 5776924615 2047233340 9820512745 1986782845 8921779227 4484244924 1328477884 7339347207 4916455204 9372383503 2386843212 9846756702 3019042367 7895385366 7513265277 0804474206 5098455069 5789930920 1331756830 1964752411 7618609327 6430444565 2701762335 1121866031 4833964288 4530617721 9259958190 2126582093 4149836867 5090484304 5176950321 1303090228 9953315696 0532263590 3965695509 1589745688 8699618906 8506789780 3075175139 6478824228 4095700326 2857686032 8065206351 8936029369 8304994910 0480687576 8645793769 4843591781 1737337169 5053087842 0346589383 1072052805 5688499538 8391009030 7584078496 6424354968 4837533387 2534588703 8202796095 7519315223 5822443211 5065053653 2014933722 9236413918 4233360145 5545934851 6905574044 3834991833 2323024413 1298776073 3043431098 0033407371 6094729450

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 ≡ 53 (mod 63)
• Q(1) is not a perfect square: it is ≡ 13 (mod 64)
• Q(2) is not a perfect square: it is ≡ 61 (mod 63)
• Q(3) is not a perfect square: it is ≡ 53 (mod 64)
• Q(4) is not a perfect square: it is ≡ 6 (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 = 839916 3039260963 1669577680 6082475779 3589904159 8989648132 2748005894 1730489236 3418082714 7674601489 0826159149 7687110506 5770462949 1461520860 7079266669 9583905565 9582256414 6519930479 2073392992 7832460345 8525100973 2659548120 1935444988 1427835759 8812862532 9985049106 4546611555 0466733128 0147989573 4463845988 9338070739 6462579212 5612522380 8618048585 3615951980 6284818256 5145955890 8499056282 1164542340 6617839150 7702343843 8911222132 5724805747 2156961760 9944242449 4191035470 1814114832 1173468797 4643884215 2332209957 0160667916 7367522817 2810451337 6276941966 8919706083 4390824915 3271493167 8204153393 7300222052 3220291933 0057822389 3214002299 5570231713 3882738146 4999585950 9153438665 6489464666 3066915795 6679557398 3396321500 2508554054 1436790251 2984448646 7440690492 1027814055 8608159835 8819597316 2016640626 4248055326 4904716952 2323958873 0216865262 0392717987 5324875601 1520843463 8291159426 2019376462 8123127029 3955234461 7959733961 5699117766 6184056709 1008492524 2455990228 3222912226 0669560083 5922047151 6358112153 7222658559 3852482550 8739413584 3682948131 9479775666 7733900808 7911717494 3625123962 2945894927 7888643907 0725325119 4728953224 6219827609 9228241838 1315230129 8620158089 5684427228 3382271971 7043703951 7683615415 4148613173 8943267284 3291419560 1895261837 6805679855 1428935530 3644543667 6300370234 5120893377 2093560794 7380523995 6347616314 5857812404 1627675714 3998511743 7407121082 0774800301 0785129426 2964176080 0807984325 0938098553 5206201881 0097892334 5751659527 2314341337 0669112468 8172842401 9545063522 7165432093 2637127909 9106129527 3469385008 3151892110 3365906475 9049662968 6297725935 8503901604 3698173371 5878255983 8367427321 9664831793 3534730329 1105620192 8150772586.

With those constraints, the unique continued fraction is: {0, 1, 18, 1, 4, 24, 2, 2, 1, 15, 1, 3, 2, 2, 6, 3, 6, 1, 9, 2, 3, 4, 1, 1, 4, 1, 1, 2, 2, 3, 1, 1, 5, 20, 3, 4, 1, 1, 14, 9, 1, 1, 8, 5, 1, 5, 3, 40, 1, 2, 5, 3, 1, 1, 3, 1, 2, 1, 8, 1, 1, 1, 4, 3, 1, 5, 6, 1, 12, 1, 1, 5, 3, 3, 1, 22, 1, 2, 2, 2, 5, 2, 2, 1, 38, 4, 1, 4, 1, 2, 25, 4, 1, 2, 2, 7, 4, 2, 27, 9, 4, 5, 1, 1, 6, 1, 3, 1, 6, 1, 10, 1, 109, 1, 1, 1, 2, 1, 88, 34, 1, 66, 2, 14, 2, 45, 2, 1, 1, 7, 1, 3, 2, 1, 43, 15, 2, 3, 2, 5, 1, 7, 1, 2, 1, 3, 3, 5, 1, 3, 2, 2, 2, 3, 1, 36, 1, 4, 1, 1, 2, 9, 2, 1, 1, 2, 84, 1, 1, 1, 1, 2, 3, 49, 1, 2, 2, 6, 1, 13, 16, 4, 1, 20, 2, 30, 2, 1, 2, 20, 1, 8, 1, 16, 17, 2, 1, 2, 1, 1, 1, 7, 5, 2, 1, 4, 1, 5, 1, 3, 3, 6, 6, 5, 1, 2, 4, 3, 10, 4, 4, 2, 1, 2, 2, 1, 2, 1, 5, 803, 1, 1, 2, 3, 1, 72, 1, 4, 1, 5, 1, 2, 11, 1, 11, 11, 13, 1, 1, 1, 2, 2, 16, 11, 1, 3, 5, 1, 6, 1, 4, 2, 2, 5, 1, 4, 11, 39, 3, 54, 4, 6, 1, 1, 7, 2, 2, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 4, 1, 1, 1, 8, 1, 1, 9, 5, 1, 1, 1, 1, 1, 5, 78, 2, 4, 83, 1, 25, 5, 1, 3, 12, 2, 4, 1, 1, 1, 4, 4, 2, 2, 2, 7, 8, 1, 4, 1, 1, 1, 1, 4, 1, 5, 1, 1, 1, 1, 64, 7, 1, 2, 5, 1, 3, 1, 7, 8, 1, 1, 1, 1, 11, 2, 3, 1, 6, 2, 1, 19, 3, 1, 36, 1, 1, 3, 1, 3, 1, 5, 1, 7, 1, 3, 9, 3, 24, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 10, 2, 1, 1, 1, 7, 6, 2, 1, 33, 1, 2, 1, 1, 2, 7, 1, 1, 7, 9, 2, 1, 1, 1, 1, 1, 1, 2, 1, 21, 3, 2, 15, 1, 1, 2, 2, 78, 2, 3, 1, 2, 1, 2, 2, 70, 1, 37, 1, 24, 1, 2, 7, 1, 10, 3, 41, 1, 1, 33, 3, 2, 2, 2, 2, 3, 2, 1, 2, 2, 1, 7, 1, 1, 21, 1, 12, 24, 1, 3, 1, 4, 1, 4, 7, 1, 1, 272, 1, 44, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 50, 3, 1, 1, 1, 4, 1, 2, 25, 3, 2, 1, 6, 6, 1, 2, 5, 5, 1, 1, 3, 13, 1, 1, 2, 4, 1, 1, 4, 4, 2, 1, 13, 1, 5, 4, 1, 2, 17, 8, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 3, 1, 3, 88, 1, 6, 1, 10, 1, 5, 1, 1, 1, 1, 3, 2, 6, 4, 60, 1, 1, 4, 2, 3, 3, 5, 3, 1, 2, 3, 4, 2, 1, 1, 1, 1, 1, 15, 1, 1, 1, 6, 3, 1, 1, 1, 2, 1, 49, 47, 2, 1, 3, 4, 4, 2, 14, 1, 1, 1, 2, 2, 1, 1, 1, 2, 8, 2, 6, 1, 1, 73, 3, 4, 1, 2, 2, 18, 1, 49, 1, 1, 3, 13, 6, 2, 24, 10, 4, 3, 10, 2, 74, 7, 1, 7, 1, 2, 1, 2526, 1, 1, 1, 485026 5654072764 9568050273 2073107105 3617278398 0404658141 2426248961 8515171279 0641423362 2578771178 7675472864 2419249739 9603889992 1074301808 5419942405 5059013497 7170628285 3839860198 8923364449 0653750298 9439586363 3309367804 6674952788 4488203690 4614903650 3460510323 9475245738 8076038359 4478454027 1545595086 7390076496 5093218892 3089273662 6146841591 0280025440 5443957956 8726248138 7254484356 2414002472 1476988979 7545089085 9840568133 4016926774 1143635467 5304994408 7506132374 1083939831 3217995426 3984113983 1738228714 4504258924 1254685868 2819070604 9592163952 3227856624 9442715699 1955697957 7586626054 9577390974 4416600497 8041523679 9818915185 1927376038 5488918589 5263443010 9110215394 5979112289 8546866091 1886040109 8352465277 3027842973 3042252149 2710658391 6337702325 7855500464 4086585729 5297891366 0217074694 6688838140 0106891682 0297638841 6704227510 4684132040 5751005829 4062538926 4463619412 3665630305 4312348127 1400394831 9742481206 5732256767 5485247887 5561755549 6625350143 5835179993, 1, 1, 5, 1, 17, 2, 3, 1, 1, 4, 2, 1, 1, 4, 4, 2, 30, 1, 2, 2, 2, 3, 1, 11, 2, 1, 5, 1, 14, 3, 1, 8, 4, 1, 10, 1, 1, 1, 2, 1, 5, 80, 5, 1, 1, 5, 6, 1, 3, 1, 1, 1, 4, 1, 2, 1, 4, 2, 1, 1, 1, 1, 2, 4, 2, 4, 1, 1, 7, 1, 1, 1, 39, 1, 1, 3, 6, 1, 1, 10, 1, 1, 33, 3, 21, 1, 1, 1, 1, 18, 1, 3, 1, 13, 2, 1, 2, 14, 3, 10, 1, 1, 1, 1, 36, 1, 1, 6, 72, 9, 1, 1, 6, 1, 239, 2, 1, 1, 5, 2, 1, 10, 1, 3, 4, 1, 31, 5, 2, 10, 1, 4, 11, 1, 1, 1, 1, 3, 1, 5, 5, 1, 3, 1, 4, 1, 11, 2, 2, 2, 14, 4, 4, 2, 7, 1, 12, 3, 1, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 2, 1, 5, 1, 5, 13, 3, 1, 5, 3, 1, 1, 1, 2, 2, 1, 1, 1, 8, 1, 6, 4, 6, 1, 1, 1, 3, 2, 1, 6, 2, 1, 3, 2, 1, 7, 1, 1, 5, 1, 78, 1, 3, 2, 3, 1, 2, 2, 1, 13, 1, 6, 1, 2, 2, 1, 5, 3, 1, 1, 2, 1, 1, 1, 6, 1, 13, 1, 1, 2, 2, 2, 17, 2, 1, 2, 2, 4, 1, 1, 19, 1, 3, 1, 2, 41, 6, 2, 1, 2, 1, 2, 1, 3, 12, 4, 8, 1, 1, 3, 3, 1, 1, 1, 15, 3, 1, 401, 1, 1, 1, 8, 2, 22, 13, 1, 2, 1, 1, 21, 1, 64820, 1, 15, 1, 2, 1, 2, 2, 1, 15, 2, 1, 1, 5, 1, 6, 5, 1, 1, 1, 1, 4, 2, 1, 1, 1, 5, 2, 1, 3, 1, 3, 1, 17, 1, 8, 1, 1, 2, 1, 57, 13, 1, 89, 1, 2, 4, 1, 1, 1, 1, 1, 1, 5, 3, 1, 2, 2, 2, 1, 17, 1, 2, 3, 1, 18, 25, 1, 1, 3, 1, 1, 2, 13, 1, 1, 1, 4, 8, 1, 3, 16, 5, 1, 19, 1, 1, 1, 1, 54, 1, 2, 6, 1, 1, 1, 1, 2, 6, 3, 1, 1, 30, 1, 2, 2, 2, 1, 13, 2, 2, 1, 1, 40, 86, 2, 6, 2, 2, 163, 1, 3, 1, 1, 23, 2, 1, 5, 1, 1, 29, 49, 10, 2, 4, 1, 4, 7, 3, 4, 2, 1, 13, 1, 2, 3, 3, 1, 16, 14, 11, 4, 1, 1, 1, 1, 4, 1, 1, 2, 4, 1, 12, 1, 1, 1, 4, 1, 1, 1, 1, 28, 2, 2, 21, 14, 8, 2, 4, 2, 8, 1, 1, 1, 10, 1, 6, 9, 1, 56, 1, 12, 7, 7, 1, 31, 1, 1, 1, 1, 2, 2, 2, 27, 8, 1, 1, 6, 2, 2, 1233, 1, 4, 8, 1, 5, 25, 1, 1, 5, 1, 1, 28, 3, 5, 1, 14, 1, 1, 1, 2, 2, 1, 27, 2, 2, 4, 1, 5, 6, 1, 6, 1, 1, 2, 1, 195, 7, 1, 3, 4, 2, 1, 2, 12, 13, 1, 23, 1, 2, 1, 2, 12, 1, 1, 1, 13, 2, 1, 6, 2, 1, 3, 8, 1, 16, 2, 7, 1, 1, 1, 32, 166, 2, 3, 1, 2, 18, 12, 2, 3, 6, 1, 1, 13, 1, 1, 4, 1, 1, 2, 6, 1, 5, 1, 7, 2, 4, 1, 3, 2, 3, 1, 3, 2, 6, 5, 2, 4, 1, 1, 1, 1, 2, 1, 1, 2, 32, 4, 22, 14, 6, 7, 2, 3, 4, 2, 1, 5, 1, 2, 1, 1, 2, 2, 3, 1, 1, 1, 65, 1, 5, 7, 1, 5, 1, 14, 11, 5, 1, 1, 1, 3, 1, 1, 14, 2, 1, 4, 2, 1}, giving these values for u and v:

• u= 37881 5494943051 4116732597 0713157197 1385344731 4797446106 4822273511 7361305102 9321849809 9872257216 2437799932 9475118520 1203115558 5441150648 2065185739 2285506505 9910394032 0363592128 3596393860 9021000428 2147335967 2308533772 1793513851 1074632580 4225133871 9193553114 3070795482 9450938325 9654497174 8751150377 1552358288 5370492741 6492784788 0025642436 4572722279 1626914468 8496183966 0476184881 0189569353 5781682767 8558886638 9996749036 3224356453 9655519429 6957015998 0154096918 5277704665 9815997722 3766310417 5193172594 6714110458 4152571750 0669931045 1867753148 3686586892 4048453592 1884415094 1040590240 6854868094 7679382954 0196723268 5592363107 8979052915 9169882973 0267872688 7598713898 3818679413 5423938105 5125669242 8853242289 4361433308 5860775134 7056400442 1284038061 2792235568 1404493519 3665586900 3969097618 3802823171 3432477840 5650403960 5052374769 5885649805 4445015166 6969854091 5841090675 3153959677 3501044501 0331362379 9176479027 8153929845 0248711862 5185349895 7041501373 4760183548 2157841246 5071779754 8544483174 6767910447 6724735129 2282179370 4721670882 1034405348 9441966519 2844382234 3071967204 4259545251 5212928475 7628488028 9984405433 6922195561 5601040325 1342746140 7915303712 3340367209 0929590051 0696210105 0211060404 9609498467 3572890624 7878166403 5324233984 9805247427 5524620852 6713997856 3033094439 7112971002 6044068852 8801853709 9885399441 2901526310 4922757415 9551798526 4548775334 2006204695 2414137358 4065952710 8933084497 4732435980 5663167588 8875992359 8150021132 7492171563 9435625722 7606769343 5058475576 1180697801 2628366047 7993500631 8699861905 5134509736 2002690035 7343485710 0302845337 5737881924 5645842870 9843222662 7707232221 0878518070 6907660684 6248947048 6665912929
• v= 39896 3514639674 4418222254 4286808702 4257344107 4264297793 6436459655 6567603983 4355440680 2896883591 9770244768 3639704399 7690880360 5093446462 6450852687 1350125005 9393031675 0435545778 0991259621 5791730877 9945739015 8863282721 4351942876 5251343567 6015514232 6529929488 0993695624 1669872581 2266359820 4107119939 4745995402 2177168535 4037903716 6563632075 5267583724 4654728188 7375610830 2607473494 6682757396 7597020178 0560905056 9109971337 0152966802 3834063901 5065724415 7204418926 5359701462 5080505172 2657322827 7286998801 8790682143 4858953269 2975688548 4922448685 8567684351 0316607698 9823799643 4321139757 7332436764 6360736594 3460209519 4345584011 0899684797 8794362314 7503325025 5356148876 2826901464 9857217957 1235012969 6606550370 7175124359 9994910755 2763764148 9784418256 8710142450 3885823771 5115077920 5072314355 7795500233 1706559500 4130867639 0521601752 1931397593 2004611469 3664484341 5053909261 8299689191 6846918645 0547773838 3741507591 3202874392 6499703718 2829714737 0125193063 8406625402 2567533826 3158445209 7237389849 3699462802 0402517178 9408090196 5569505631 6192364049 7648550817 4580146305 0406995854 6787738731 3449600871 6993121551 9743856161 1946144100 2130096381 1342093763 8445479243 0733965103 9606703239 0530287195 2239471315 2459319122 4491037626 2245968659 3267332481 2396484843 7076610420 0409228670 2862477497 6673859551 6844732258 1715051412 6780612095 9296870658 5868034162 3629732161 7256810426 7854869624 1042386793 2362112351 0490018346 9215505630 8602940605 3906597596 0108599385 2951920645 2394361762 7523295390 9507217450 9497778547 3228128800 1443049781 9050091984 6348000975 9007792422 1103678882 2600314207 4858176373 7139030578 6266365049 8698880154 4821804557 2428595168 4367540360 9490274621

We also need to calculate d = floor(c₄·v/F + 0.5) = 1507 3604712006 6271647048 1589238904 6663300998 3128223495 7418042269 3014730161 0671337793 7456570510 7059493498 0470668099 1331054293 9549990965 8623594086 4757538998 6580491313 2239680160 2378897270 9802965052 4043771389 9566655329 0141084092 4498705560 6038297228 7273382111 9906328891 6814916897 3650913496 7587437945 4002682890 3906231532 4049770719 8966740224 5838441466 3250704780 8811317320 7767155540 7807804097 9472866751 0295927287 5010681677 0645698405 1018788294 7932323289 5952685264 9494410406 4240838683 4500780529 3524667725 5453579285 7714631339 0746399598 6446676801 8067204564 3012815808 4030004742 0168130137 6821119141 1865779443 9440127523 8802125549 7482669657 2941871116 0021929160 4801373066 4993157953 1911669759 8149947183 1152530994 2432337801 5071305261 3960900804 0026752582 9599863233 4076935263 6386802098 5806316318 0770570827 9562301739 3614289557 1437358686 8909004649 6644471254 1898073207 7778485149 0021687604 1253706609 6888648736 1276324429 6127425822 0977158033 1684520797 3892955061 1275926968 1819152257 4942815586 4993561661 5134674487 4825265174 7062684339 3106039015 6990830072 5724443267 4333007819 0417573285 9206296802 0215757163 4633303804 0013573731 0938800656 2092162323 8487537927 1726843206 1111118032 8422118424 2183264997 7052100048 9845195900 7495889778 4189005324 3760898506 4649603217 2526887589 1507606694 1193784543 8018115610 8864568883 1604587994 3525404995 9190763868 5206161074 3525745448 4978487226 1479384149 8687858565 8444759637 1986677222 1450254541 4725497240 1195122245 8682072241 5736485723 0023104057 6319296899 4350565282 5380923226 3035293149 5184515631 5053957131 2934161778 9973280150 2088600053 2013281287 6242973186 9026659673 7781939724 5486283514 4916065906 7946369047 5365767133 3917553939 8568071982 8150887746 1410066789 1472398766

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₁= +39896 3514639674 4418222254 4286808702 4257344107 4264297793 6436459655 6567603983 4355440680 2896883591 9770244768 3639704399 7690880360 5093446462 6450852687 1350125005 9393031675 0435545778 0991259621 5791730877 9945739015 8863282721 4351942876 5251343567 6015514232 6529929488 0993695624 1669872581 2266359820 4107119939 4745995402 2177168535 4037903716 6563632075 5267583724 4654728188 7375610830 2607473494 6682757396 7597020178 0560905056 9109971337 0152966802 3834063901 5065724415 7204418926 5359701462 5080505172 2657322827 7286998801 8790682143 4858953269 2975688548 4922448685 8567684351 0316607698 9823799643 4321139757 7332436764 6360736594 3460209519 4345584011 0899684797 8794362314 7503325025 5356148876 2826901464 9857217957 1235012969 6606550370 7175124359 9994910755 2763764148 9784418256 8710142450 3885823771 5115077920 5072314355 7795500233 1706559500 4130867639 0521601752 1931397593 2004611469 3664484341 5053909261 8299689191 6846918645 0547773838 3741507591 3202874392 6499703718 2829714737 0125193063 8406625402 2567533826 3158445209 7237389849 3699462802 0402517178 9408090196 5569505631 6192364049 7648550817 4580146305 0406995854 6787738731 3449600871 6993121551 9743856161 1946144100 2130096381 1342093763 8445479243 0733965103 9606703239 0530287195 2239471315 2459319122 4491037626 2245968659 3267332481 2396484843 7076610420 0409228670 2862477497 6673859551 6844732258 1715051412 6780612095 9296870658 5868034162 3629732161 7256810426 7854869624 1042386793 2362112351 0490018346 9215505630 8602940605 3906597596 0108599385 2951920645 2394361762 7523295390 9507217450 9497778547 3228128800 1443049781 9050091984 6348000975 9007792422 1103678882 2600314207 4858176373 7139030578 6266365049 8698880154 4821804557 2428595168 4367540360 9490274621
• z₂= -22493 7377583750 0307858731 2645002117 5599615136 5858479191 1471967888 5676253910 1268443346 8239167211 9682284096 9192959615 1455999703 1664877118 0387573744 8333459013 1431631466 9010570118 3043536466 7292751159 1522065842 5753322448 4951417746 6839070424 2635033716 6329526692 6345919843 3785380735 1342503511 1243242110 4946536056 2711387857 2153965569 7479238799 9253547925 3233959665 0686281463 7501157329 8927467510 7171359313 0400789341 8016318264 7482900815 0450319473 3306931801 4717348647 8455589682 3690721327 0050948103 1242048843 2945469981 6534926620 1509040355 6421678909 3831226559 7413341476 7336658773 1281836293 1045797137 4376274847 6869026278 0906614673 2910938505 7719145876 3086357434 8828992592 6826804855 0112682022 6037908634 4326216637 6058568469 2358779294 7203446987 4119856078 2709952568 7212244929 0142744364 0639729626 2929297167 1154956031 5553152277 9396091123 9164020274 3882923882 3467537368 7378723996 4452670464 6287184554 8194800681 5503677208 7732381067 9761856088 9145802315 8167366172 7273942205 2530278994 3716740880 4062127763 7260285998 9066842861 2466098119 5564807375 5854174159 2988853795 0675213401 5112389273 3746846643 1157276234 3129501900 3790592028 0239833150 3771412227 9104152987 4855230320 8182922511 1053209766 9032647609 7703394912 9310189957 8597685356 7732683328 0626655523 7100401204 9044226531 7439613605 1391222965 0712730998 6680000313 2318049490 0626308595 2017018799 7207778950 9054372210 2987223269 5374771696 3674722202 8288844193 1614939920 6689432942 8447061262 1920177696 3514092854 0673397621 3168849971 9527660457 1424817916 9271951329 7706227658 3086615699 1654228886 8762371912 9062609578 4940650440 6617912220 6198939884 2566707419 8608182086 5986618672 1339937598 7640014447 9958513967 6944436326 8632464432 7403495685 6170022323 7439868837
• z₃= -1 1261785546 6653305598 1958409758 9707319918 4150853497 7913737383 7706931619 9661359727 4774191271 8151007975 6166823425 9374553192 8005424601 9130180765 0720857827 1790106681 1988829364 5142950790 9976997981 7989607797 8967245103 6980223329 5035929249 3477316707 5702174239 1654754675 4278659401 9007751365 6892150822 6083017186 9580089203 0582917918 5916944335 3284948119 2223610040 5172856601 8471786737 7389306747 1130476436 4262314379 9929961162 8633448901 6483019332 6230383658 8248876696 8132207455 9373823296 1828063068 3094637163 6164723465 4832214630 6032064459 3706733393 6765852788 5255644079 9918692990 7772098860 9994741155 5676664091 2925970118 2310444885 2988516081 8518038424 8085770189 4872073605 3778871778 4376765794 0368735301 3840974119 8469555513 7936439801 7979325883 6890565727 1094316521 4822179178 3731058540 1666526043 2245601965 0253496538 3689662293 6606275038 3728774201 3336864662 8150337063 1848750621 4786974171 1067113989 8731472052 0248580059 8315645195 1703919601 7018749503 3590484539 5893993901 4642881140 8287767375 4166888381 8699198346 5796677536 5669418950 5452305235 5059878037 5119687379 0479545968 2215660797 3509084488 3904523120 1072049982 2470902282 2581716119 9205741682 2481800209 2734384549 6761752470 0197322177 8511583934 3779179999 6599782875 0359071065 4404622706 3608356023 7680391136 6011761409 0852412711 5575396944 5548811487 0170128000 0083465625 5181337313 1735284589 6400439950 4162231832 2790867171 4448723958 9167538866 4593136194 5260338541 1766386887 8458779353 2830844112 8367507459 1676689498 5883248215 6228510098 6176726930 2393603389 2045863667 2141600096 2315212874 0901551364 9421666385 8207285941 5397946080 9515897730 6426460580 9906594115 2149185052 5965339852 7910072501 7287632477 2915830694 8174618213 1484515000 6630070584 7146710916 4818205118 8749335027 8083762935 1627721303 3642592892 9897729598 9614609390 3349402320 1838076836 7461558539 8088736314 2172534628 7295924941 5873120659 8091827492 3891541892 0756278351 6313863138 2093792067 5448053063 9218974890 1438876134 7504932087 1867612451 5753517487 4947830398 5753698993 1992525019 6393191526 9499602651 3120851594 4713270645 9333434338 4701731625 4880877945 3273120788 4459573602 6478175569 5930634984 6501716420 9737700377 6768122583 7048004350 1747350619 1108088938 8432309952 6432529560 5932159409 0838786480 3014441071 3569824855 1249934948 6280209128 7910707183 4646682572 2708517612 9284471298 8284661379 1471815488 0789842123 0122383746 5594077107 5611186329 4865816309 2942340473 0920507754 3822112267 3409653225 9193832098 9283049627 2908738019 6814774628 6272983540 4797613595 6852282222 7531318155 6415657105 7880085940 6428608590 7046742466 7806323730 7028027988 8147575515 5149745290 1509183342 8001318638 7489940768 6074019396 1001546248 2094364573 9559002419 7788429369 9735326162 1935162930 9897581954 4007243584 6777063077 1204234508 9661357023 5929518169 7364149991 7742988475 8483317566 9406379491 9604505508 1891568462 3185539968 7808370558 0473424941 7975033483 0955656293 6331676331 4006041409 4723985076 7757280329 5291971166 5557125684 1944144950 7209631555 9255449314 7488484687 6638874159 7333943328 8852409665 5668733425 7959259258 6240816356 8871186677 8603480751 5727014075 0142641690 8237581523 5352592116 7364570094 1724690933 6861403617 7239248617 9019719537 8248319942 7092702968 5155789547 5617901488 8789768921 7981097550 1734304369 3164990686 7230832732 8229899198 3005770666 3965822872 4648749718 9037080390 2039281934 8425875016 9710415384 6627732939 7615785078 0325203071 4451773348 1241961473 3023473749 0732197085
• z₄= -1507 3604712006 6271647048 1589238904 6663300998 3128223495 7418042269 3014730161 0671337793 7456570510 7059493498 0470668099 1331054293 9549990965 8623594086 4757538998 6580491313 2239680160 2378897270 9802965052 4043771389 9566655329 0141084092 4498705560 6038297228 7273382111 9906328891 6814916897 3650913496 7587437945 4002682890 3906231532 4049770719 8966740224 5838441466 3250704780 8811317320 7767155540 7807804097 9472866751 0295927287 5010681677 0645698405 1018788294 7932323289 5952685264 9494410406 4240838683 4500780529 3524667725 5453579285 7714631339 0746399598 6446676801 8067204564 3012815808 4030004742 0168130137 6821119141 1865779443 9440127523 8802125549 7482669657 2941871116 0021929160 4801373066 4993157953 1911669759 8149947183 1152530994 2432337801 5071305261 3960900804 0026752582 9599863233 4076935263 6386802098 5806316318 0770570827 9562301739 3614289557 1437358686 8909004649 6644471254 1898073207 7778485149 0021687604 1253706609 6888648736 1276324429 6127425822 0977158033 1684520797 3892955061 1275926968 1819152257 4942815586 4993561661 5134674487 4825265174 7062684339 3106039015 6990830072 5724443267 4333007819 0417573285 9206296802 0215757163 4633303804 0013573731 0938800656 2092162323 8487537927 1726843206 1111118032 8422118424 2183264997 7052100048 9845195900 7495889778 4189005324 3760898506 4649603217 2526887589 1507606694 1193784543 8018115610 8864568883 1604587994 3525404995 9190763868 5206161074 3525745448 4978487226 1479384149 8687858565 8444759637 1986677222 1450254541 4725497240 1195122245 8682072241 5736485723 0023104057 6319296899 4350565282 5380923226 3035293149 5184515631 5053957131 2934161778 9973280150 2088600053 2013281287 6242973186 9026659673 7781939724 5486283514 4916065906 7946369047 5365767133 3917553939 8568071982 8150887746 1410066789 1472398766

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)
• -53129659 9102665687 4240293222 4651744006 9002486613 1732407994 7759720334 1486587079 9020377981 2291538306 4812492462 2396689576 9603063734 4323577353 8487689130 7206360299 9808014845 0880833007 1182858560 3063479370 5163237138 5694381999 3948443393 6574289075 8694629158 6534911189 8175483052 7058013164 5874373546 5790328244 0065448295 8341337144 1277808902 0818963192 0912604475 9356198790 9748556149 7374275082 6400934865 1216825231 1933089273 2325925168 7620075043 1896443941 2080416096 3674358198 5255904114 0122866743 9833238366 8228221458 1346505732 7577939453 4117105602 9693335738 6812737166 1900423532 4177554999 7916004587 0351072288 9488991702 9046883261 7687312686 3499110068 6607288318 4419861890 3036405396 4613395751 0711744517 4062756028 4177095323 4487658339 8651597540 3281351277 4749533957 7194180295 4213696459 3031601513 4855835265 1041089165 4100380701 4677436407 5367863659 0645211425+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• +53129659 9102665687 4240293222 4651744006 9002486613 1732407994 7759720334 1486587079 9020377981 2291538306 4812492462 2396689576 9603063734 4323577353 8487689130 7206360299 9808014845 0880833007 1182858560 3063479370 5163237138 5694381999 3948443393 6574289075 8694629158 6534911189 8175483052 7058013164 5874373546 5790328244 0065448295 8341337144 1277808902 0818963192 0912604475 9356198790 9748556149 7374275082 6400934865 1216825231 1933089273 2325925168 7620075043 1896443941 2080416096 3674358198 5255904114 0122866743 9833238366 8228221458 1346505732 7577939453 4117105602 9693335738 6812737166 1900423532 4177554999 7916004587 0351072288 9488991702 9046883261 7687312686 3499110068 6607288318 4419861890 3036405396 4613395751 0711744517 4062756028 4177095323 4487658339 8651597540 3281351277 4749533957 7194180295 4213696459 3031601513 4855835265 1041089165 9738424515 7474318279 5497953949 0054298107+ε∈(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.