Primality Certificate for (1710^2281-1)/1709

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.439573% 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) = 30.439573%

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

Express N in base F

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

• c₁= 1109 5733740277 4238281583 9242221907 4994463262 0480692630 3695717493 9960583389 8045116022 7481589158 8102636969 4890345339 6783815928 3711327360 6674198660 0587050597 9309720717 9422427797 5961016710 4856103459 9283825246 0119502847 1787090221 6592841984 4398374566 4823907044 5481243879 7736447864 5748476516 4585607054 5731465531 2516294082 3321541424 7971836987 7104408609 6438962668 0441694598 8018460319 3508779660 0051313258 2531585585 9549571138 8785132365 1260450417 9200245237 1909399938 1902982045 3994013580 9179116111 3939319901 6437101557 4640495043 5561858579 1531471622 3258092916 5505908175 9397810243 8793711637 0514785417 3079539862 1865935874 0209079326 4725912624 2441286535 3386613169 2305464288 3608733159 4482607074 8848094398 3779705225 6488966497 0963617542 5644041280 1781355549 2174698261 6557990785 7569154267 1381140036 2144016785 8401613207 1563576895 6348719952 0298266001 7360028044 0222620273 6890093134 1858038441 2324997825 6702540964 0375315384 5414798180 8334465042 2362123983 6036418918 9679917158 9999841119 3524952757 8058677555 2361483397 9243082873 8338096298 8222445211 9266782365 1028914532 7868600050 3873414561 6577625214 6919465420 8986144971 9941525130 7776061881 8042918185 4755515521 0256742444 3121943251 4720254741 1302583828 6784011671 8646135199 7543039192 8268419187 7089516701 7505591440 3705094626 0581492864 1894902214 0274904549 3550518294 7905031821 5046399155 7766840134 0687202689 3443273189 5892332124 2595810891 6641799006 5304285877 3674742580 6705559070 3695972981 1045651008 5730299151 1391021933 0426098344 4990787484 7756331601 1836489677 6172395734 9933815458 8907622297 9506311580 6495770096 1637698799 8736186754 2568120317 4765071931 5257469207 0620634763 9307732652 0958938530 3734842660 9118954756 9453750842 4822337669 0691565529 3020543071 5221525905 5506998911 4837770105 5282835355 0818731889 6027643970 7646447268 5489973281 4098832413 1883893032 3164731472 3011187905 5838637400 3543566738 6421565280 6757533303 0015419405 7789885514 3745039623 9620365286 0575302708 6246150832 3661274033 3333486722 2010083924 5343788859 9245492889 7517823216 3350274593 8528220072 1969335226 3987010140 2508813809 6657026921 5434601557 2521739491 4915389075 4701015364 9965808994 1403468560 3740025282 9298736923 6360540659 7199197816 5933653505 8404393643 5144576082 7141784994 7941527886 8088071027 0506494302 7870960630 9878766985 1142421273 7250038888 3834979467 6264239493 8631884191 8192292807
• c₂= 3391 1095102491 2418460099 8839996274 6997083154 5635101028 5907569104 1330997379 6546191570 9296744697 5814954861 1920803356 4426934975 9495902685 5387886086 7807607612 1946414896 4610363300 4052313157 5484053265 1239769205 6195327087 8942152760 6358965233 5703538474 9381136060 5428987271 7857377071 9435700249 5726821167 5653840277 5830238293 8680609726 8180968075 7460131231 9845871344 0453718001 2855670787 8758923278 7686820812 8688624142 2104353047 2304477422 6737796860 0466290404 0859028600 1322940713 1194782450 4093235148 8318780455 8375802842 6551863820 4394123690 4260702625 1272142106 5495364685 2996037808 5949566095 5437895050 2223276436 4652831699 6595268177 9713444925 7051241437 4022598441 1840527993 2755956194 9733147753 5624886913 3259876276 6920022871 6906621386 9860052654 2221335481 5085452729 0516832544 9465767601 3309526834 3512858295 4167521004 2453051631 7133126887 2027943044 9204322094 4773883672 7764488487 7436737020 0640055412 2154856969 9679573573 8866355448 3493882929 5817741151 5464845335 6467829913 3721919350 5638408555 2013500377 5379352970 4162346897 1729857124 4096929908 5645290713 6003974314 2857114292 5229947576 9774806041 5507131195 0729777640 9903875588 9275062629 2233505387 5187167621 2802450606 5947072520 5430919460 8165279325 1102292845 6295063236 5248529571 4808962524 0716263540 0194272292 8134902794 0967559647 7674176103 0422427908 9189173828 6199946345 1804420589 5269476854 7948273670 1184027584 7695278935 4599460874 2809415826 4340577110 9940819716 1341968665 6776488967 2834708412 3325764826 4234516442 7814807647 2441054142 5735499341 9647450054 5943844605 6087522902 8310644355 3812402121 3776640826 8670426283 6106835721 1939385649 6573031799 9635694174 6736793648 4594485599 3174426664 3622210071 1423581906 5277698615 0656387983 2560199749 3057688486 7716364019 9950629344 7897911843 9472608722 1273650806 0938798615 1430023207 6110624007 6758027710 5265783786 5080387582 5008381399 3312643228 7141061761 4407529598 0889967114 8226076773 0710389132 7796951369 0833847887 4251941553 8880023458 9445790271 2728515456 5994916975 5843743658 4454097544 6476152334 8201820151 0629473600 8970791931 9589419454 3255128890 8746372885 0433435436 9253152072 2721462030 7062323273 3521909189 7166129584 2643341855 2772856750 5274734587 7803703034 7166365094 0739109042 4222666993 0183167186 4563580353 0208061127 8664662967 3883230148 0044538688 5165981618 8541392085 4822837674 6441745493 0415257140 9706764768
• c₃= 8267423102 5814648628 8875653276 0600501469 9628169568 6442600345 7664591995 4721251778 9335644497 0118566697 7864367408 5798718664 8624740376 9864880567 6692979485 6898905765 7984629011 6455898490 6535035891 1877799571 1362490477 6057837705 1032227341 3977091285 9041805516 6316869866 7361966284 6265310092 6367218159 8462930638 0763277728 8397755793 6282907275 9159361308 3719629320 1810974058 2054379133 3246601884 3629135548 1411747492 4963312050 0981569958 0543377052 7022150890 2511446978 1147587009 5482856006 2060580953 5513002273 1521690803 6826274977 9600211185 4925698914 2894378864 5454965581 2047820311 1595766073 3568634386 7223252441 6563839594 9244886856 5654375344 0854314678 5544892942
• c₄= 4883 2469783635 6996032824 9737320732 1862787057 2376708354 2130394657 7052128061 0792608091 0109075859 2375164345 7435604516 1394845453 8489944628 0953751047 2479445702 9689935909 0396626539 7183614460 9584678697 6962070604 8638082290 6726541804 6832779114 3728955911 8461853107 1145968260 5007368459 4963676311 2909365400 3814232495 0783242229 3194748843 0105816878 9367790747 8733645364 7557675736 1219941172 0053157795 8951069306 8325704851 1360076387 3300033010 3655763783 0679154714 3011152171 6050268328 6180119716 0811061859 4692882688 0011879842 7119954254 2490827544 1602683850 1726531968 0004183781 8473106661 5807192701 5365217602 1279974396 5923499907 2586285764 2790543845 6949033988 4673382538 4283556585 7260704408 8975389169 1774655944 9477549784 5545416223 0921839510 0176119952 7115993658 7889959766 8240004189 6334008773 8824610956 7342764540 9297966466 2737156194 5226569192 4097141112 9921537430 4325997052 4905261017 3383122599 1324426341 5620078550 1414788760 6904717630 0422109755 6255241857 5525892860 0417819191 4362499408 9702567680 9550328677 6538390951 8093130170 9541642568 0323403298 7680464810 0967535973 4819835434 4521449003 6371695697 6414404503 7749363180 8222179226 0494225139 3394737778 3353851628 7085323062 3421745483 6070462146 8774834416 0208892974 0217898845 1814493562 9626474142 9521889373 2619464215 2236906806 4014065519 6817835032 0197085080 5604925452 8364715971 5987152535 2804279134 7851777967 5764489458 2211590546 0861919050 7714820521 4514228706 0972936414 8366682866 9448017680 5486594368 3710593077 6169242494 8015965942 0129053368 2607891140 1261778761 1572134470 8836215520 6953056232 6609663791 4661287342 1519041808 6051928481 5774244141 3960220716 3132103397 6312564322 5322587590 5174571607 0855654154 2605921652 2620101811 3944436596 8533986569 8962209056 6888335156 0642566388 5434550031 5643771618 0129624050 7888772406 7494070676 3205592425 1796709141 1359105710 6580833475 0890629809 4629672908 3074240598 1183244797 9907764223 7852300816 6100809151 7571985644 2461263126 2356753416 5360291114 1309775766 4682658489 7902849010 9855369254 6132155711 0825421720 3216973538 9453590918 2507266353 1379942553 0955580299 9021516790 5763675552 8746648968 4813921353 3821060888 7585218213 6673053864 3117282115 7951197371 0990666573 4722163692 0674690693 6421784447 8967635887 7184758338 7618188524 8548707705 5692840968 8848431048 6222467141 7575165189 2280585246 1093670072 1475202265 1464431065 3526142065 6158190177 6974590655 2823568060 6032245439 4410582904 7376301656 5097280569 3684099662 7539451600 6267694949 0856180852 3017828214 6808103678 1258155921 8313926349 7858745940 3420992052 4453515910 6104872235 8814878183 3273921813 3023153144 5938237970 6966009614 1331745145 7814616766 3306230132 6923472651 9660971146 9855616735 8171652540 3972629615 2028867409 7433440665 1410519448 3057553414 2342559186 8146027798 0243295997 9246218865 3138789142 3768880810 9303231718 6242922279 1980371026 7125748353 8486479407 3844302433 5675309784 9611600185 7511917761 1770083963 6690746764 1676432347 2575874018 4440545797 7783789423 1379092603 8945969063 8586687294 7371121197 7297276934 2327868784 8392701428

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 ≡ 5 (mod 63)
• Q(1) is not a perfect square: it is ≡ 45 (mod 64)
• Q(2) is not a perfect square: it is ≡ 13 (mod 63)
• Q(3) is not a perfect square: it is ≡ 45 (mod 64)
• Q(4) is not a perfect square: it is ≡ 21 (mod 63)
• Q(5) is not a perfect square: it is ≡ 29 (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 = 84 5248056555 7620404520 9882986525 2493641161 0431696983 6892557752 5481538543 5992525998 4376168672 9433584647 6936338248 4715888223 9730284118 4198404451 2168369287 1415711005 7977830938 1527327498 7749335346 8276063830 2892898606 7565529685 5027795994 3764833623 5863508696 0816521884 2068752572 9238965794 4888449278 8436568961 0320305330 0324766827 0582197043 3130783405 9220652170 3837074518 3202177598 3992349090 6592152189 6273560671 6447335000 3139029438 4020023544 6566320858 5311683359 0093689079 8394022267 9698493314 5048401391 2902884720 0491334106 2631716301 4463729714 1755638157 6096119046 7104509599 0704847344 0566127800 7079358243 0486042841 1720319290 0868888724 9555006378 3705859944 8919775107 1430093922 8396064936 8011101824 3067258432 1446519949 5315984273 5568393922 4001889057 7374902908 1287871350 3393439888 9974393078 8048204406 7418273461 6873558423.

With those constraints, the unique continued fraction is: {0, 5, 3, 10, 1, 3, 4, 1, 32, 1, 1, 4, 1, 7, 1, 1, 1, 2, 6, 2, 1, 1, 1, 2, 1, 2, 1, 5, 2, 1, 7, 45, 1, 10, 2, 8, 2, 9, 1, 2, 1, 108, 1, 79, 2, 2, 12, 1, 2, 2, 4, 1, 2, 1, 1, 3, 16, 4, 2, 1, 2, 58, 1, 1, 3, 1, 7, 1, 2, 5, 2, 1, 2, 2, 6, 10, 1, 3, 9, 1, 4, 1, 2, 8, 3, 65, 1, 8, 4, 1, 5, 1, 11, 2, 2, 2, 1, 1, 5, 1, 11, 1, 21, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 4, 1, 1, 2, 2, 6, 1, 1, 2, 1, 45, 1, 2, 4, 1, 2, 8, 1, 1, 1, 4, 3, 1, 6, 3, 3, 1, 11, 1, 1, 1, 1, 4, 5, 7, 1, 3, 22, 3, 2, 4, 2, 1, 900, 2, 2, 3, 4, 1, 35, 4, 1, 1, 1, 6, 1, 42, 12, 1, 1, 1, 3, 1, 2, 7, 3, 45, 1, 2, 3, 1, 1, 1, 1, 2, 1, 5, 1, 13, 7, 1, 1, 6, 1, 1, 18, 158, 1, 2, 2, 3, 4, 7, 2, 6, 4, 1, 5, 1, 3, 1, 1, 3, 1, 2, 8, 1, 2, 3, 1, 1, 1, 10, 1, 1, 1, 11, 1, 110, 1, 2, 1, 3, 1, 9, 5, 3, 1, 3, 1, 9, 13, 7, 2, 2, 3, 2, 1, 6, 1, 1, 2, 7, 1, 3, 1, 1, 3, 1, 15, 1, 4, 2, 1, 1, 11, 11, 6, 1, 7, 3, 18, 2, 1, 5, 15, 3, 4, 1, 1, 5, 1, 2, 1, 4, 13, 10, 1, 1, 2, 14, 39, 1, 18, 1, 1, 88, 1, 1, 1, 13, 1, 78, 1, 4, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 2, 1, 6, 4, 19, 1, 1, 1, 1, 21, 1, 2, 5, 2, 1, 6, 18, 1, 1, 5, 3, 6, 1, 252, 3, 9, 1, 5, 3, 1, 8, 3, 1, 31, 1, 1, 5, 2, 1, 1, 2, 9, 2, 2, 1, 5, 3, 2, 41, 1, 2, 4, 2, 36, 1, 4, 29, 1, 4, 82, 1, 20, 1, 2, 3, 6, 1, 4, 4, 1, 1, 1, 1, 2, 3, 1, 4, 8, 2, 1, 3, 2, 16, 1, 3, 1, 1, 6, 7, 1, 3, 4, 5, 6, 4, 1, 2, 1, 33, 1, 23, 1, 1, 1, 1, 10, 3, 11, 1, 2, 6, 7, 54, 4, 2, 2, 2, 1, 1, 8, 13, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 8, 2, 6, 5, 1, 1, 2, 2, 130, 3, 1, 4, 1, 1, 2, 14, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 6, 5, 1, 1, 1, 4, 1, 1, 29, 1, 1, 2, 2, 1, 1, 7, 9, 1, 1, 4, 1, 6, 1, 1, 3, 8, 2, 1, 5, 1, 1, 3, 66, 1, 1, 2, 1, 1, 16, 2, 4, 1, 1, 2, 8, 1, 2, 9, 4, 1, 77, 122, 3, 1, 4, 1, 4, 6, 1, 11, 18, 1, 1, 15, 2, 12, 5, 2, 1, 1, 3, 1, 1, 1, 3, 3, 1, 3, 4, 1, 1, 2, 1, 4, 1, 1, 2, 2, 1, 1, 9, 4, 2, 3, 1, 2, 6, 136, 5488, 1, 1, 419, 2, 32, 1, 5, 5, 1, 1, 1, 4, 4, 2, 1, 1, 14, 1, 5, 2, 1, 1, 4, 5, 1, 1, 6, 1, 153, 2, 1, 5, 2, 10, 6, 205, 3, 1, 2, 1, 2, 38, 1, 4, 2, 1, 6, 1, 1, 1, 3, 1, 1, 2, 3, 4, 6, 1, 12, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 5, 1, 1, 1, 7, 1, 4, 6, 1, 3, 2, 2, 2, 27, 1, 7, 1, 3, 3, 2, 12, 1, 3, 4, 1, 5, 1, 1, 3, 11, 1, 1, 2, 1, 3, 155, 3, 1, 3, 1, 1, 1, 3, 1, 8, 1, 8, 79, 2, 2, 3, 1, 2, 1, 12, 1, 2, 8, 3, 2, 8, 2, 1, 2, 2, 1, 3, 1, 1, 4, 7, 2, 6, 1, 4, 1, 7, 12, 4, 1, 2, 1, 1, 3, 6, 21, 3, 1, 3, 6, 2, 1, 2, 1, 1, 1, 2, 2, 2, 9, 4, 16, 2, 3, 3, 58, 3, 1, 5, 2, 1, 3, 1, 1, 1, 15, 2, 21, 4, 1, 10, 1, 4, 16, 2, 10, 13, 1, 10, 3, 12, 5, 1, 1, 26, 5, 3, 87, 1, 3, 2, 1, 1, 1, 11, 1, 6, 35, 2, 1, 1, 10, 1, 6, 1, 1, 1, 2, 7, 1, 4, 1, 17, 1, 1, 2, 8, 2, 1, 3, 2, 1, 1, 1, 5, 1, 6, 1, 15, 1, 15, 85, 1, 1, 1, 13, 26, 18, 66, 1, 1, 42, 1, 2, 1, 3, 1, 1, 2, 1, 5, 3, 19, 1, 12, 4, 1, 1, 21, 1, 4, 4, 1, 3, 3, 1, 6, 1, 2, 2, 7, 5, 1, 1, 3, 2, 4, 1, 6, 1, 12, 2, 1, 8, 1, 29, 3, 1, 1, 1, 3, 4, 3, 1, 2, 2, 65, 1, 565, 1, 3, 2, 2, 8, 5, 20, 1, 2, 1, 6, 6, 8, 1, 2, 1, 2, 8, 2, 17, 3, 2, 2, 3, 1, 3, 1, 2, 1, 19, 1, 5, 2, 2, 2, 7, 1, 5, 14, 1, 2, 3, 2, 1, 1, 20, 8, 3, 13, 1, 1, 3, 2, 6, 1, 2, 11, 3, 2, 1, 6, 9, 2, 3, 1, 1, 3, 4, 5, 1, 5, 3, 14, 2, 3, 3, 41, 1, 13, 2, 4, 1, 3, 1, 2, 1, 2, 5, 13, 1, 1, 1, 1, 1, 5, 1, 5, 2, 1, 2, 9, 4, 2, 6, 1, 3, 3, 4, 1, 2, 15, 1, 5, 1, 1, 1, 133, 13, 7, 1, 1, 5, 8, 1, 166, 1, 4, 1, 3, 1, 7, 2, 13, 1, 2, 10, 1, 1, 4, 1, 1, 3, 3, 5, 1, 4, 1, 6, 2, 14, 20, 4, 1, 15, 9, 1, 13, 4, 1, 2, 5, 1, 1, 1, 4, 1, 47, 1, 12, 4, 4, 1, 1, 1, 21, 1, 5, 2, 2, 1, 2, 5, 1, 8, 3, 1, 3, 62, 1, 2, 1, 2, 17, 1, 1, 12, 1, 1, 4, 1, 3, 4, 6, 1, 8, 7, 1, 11, 4, 1, 3, 1, 2, 3, 3, 28, 1, 36, 1, 2, 575, 2729, 2, 32, 1, 7, 2, 40, 2, 3, 15, 1, 2, 26, 2, 1, 6, 2, 1, 3, 1, 3, 1, 8, 89, 4, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 39, 1, 1, 1, 9, 1, 1, 2, 3, 5, 43, 16, 3, 2, 1, 7, 2, 3, 4, 6, 1, 2, 1, 525, 1, 5, 2, 4, 9, 1, 2, 98, 11, 6, 1, 1, 1, 4, 1, 11, 2, 24, 13, 3, 6, 11, 1, 2, 1, 3, 1, 1, 2, 1, 1, 11, 1, 7, 3, 1, 37, 1, 1, 1, 1, 6, 1, 1, 3, 3, 3, 1, 3, 2, 1, 70, 4, 7, 1, 6, 1, 9, 5, 1, 1, 2, 2, 2, 1, 1, 1, 1, 14, 1, 2, 23, 2, 1, 4, 2, 1, 1, 2, 229, 2, 5, 1, 8, 2, 1, 186, 1, 3, 3, 18, 1, 1, 1, 1, 13, 8, 1, 1, 1, 5, 4, 6, 9, 1, 2, 1, 3, 6, 1, 2, 2, 1, 48, 1, 1, 8, 1, 4, 28, 1, 4, 1, 17, 1, 1, 3, 14, 2, 1, 1, 160, 2, 8, 1, 4, 1, 2, 15, 1, 5, 3, 3, 2, 5, 5, 1, 7, 4, 2, 5, 1, 8, 1, 8, 1, 1, 1, 1, 2, 3, 1, 46, 251, 3, 42, 1, 1, 171, 3, 1, 2, 4, 18, 1, 2, 1, 8, 1, 1, 10, 1, 4, 1, 4, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 2, 1, 32, 1, 1, 2, 1, 3, 3, 2, 7, 2, 1, 3, 1, 1, 5, 13, 1, 1, 2, 1, 1, 6, 14, 3, 77, 1, 2, 170, 2, 2, 1, 2, 1, 3, 1, 4, 1, 5, 1, 1, 9, 2, 2, 5, 1, 3, 2, 2, 1, 1, 1, 1, 5, 2, 2, 22, 3, 2, 7, 1, 1, 11, 1, 1, 1, 3, 6, 1, 5, 1, 9, 1, 6, 31, 1, 10, 1, 1, 1, 10, 2, 2, 2, 1, 2, 5, 1, 1, 3, 2, 3, 1, 2, 2, 1, 9, 1, 5, 1, 3, 1, 5, 2, 7, 2, 1, 1, 4, 7, 9, 1, 10, 1, 2, 1, 20, 4, 1, 1, 1, 1, 1, 3, 3, 2, 1, 4, 4, 5, 5, 3, 1, 2, 1, 2, 7, 1, 2, 1, 9, 1, 3, 1, 4, 1, 3, 2, 2, 1, 5, 1, 1, 6, 3, 2, 7, 1, 1, 4, 3, 1, 1, 5, 1, 1, 2, 1, 9, 1, 1, 1, 4, 3, 1, 6}, giving these values for u and v:

• u= 6 9362864727 8338975469 0757924430 5680753047 2147083424 5334963318 3359689988 3097231040 1003403478 1869880893 8466429952 1316846274 5396532616 2237356038 2302427386 5899267656 6133819969 6938365234 2327010940 1067044865 9409153944 4884697598 3194615163 5310597184 8662667149 0634297512 5588711712 0952861876 7404139657 0636522657 4897818097 2166811043 5526110202 9266715287 7820535596 4030208015 4031007504 3803681842 6277165838 7159342667 5248745301 4614179690 3231870194 8910621928 6621557291 2660714416 4127560387 8658249705 7130828251 3944897101 0220151397 4319463031 3582977939 8114611221 9300384375 3870290729 5060369522 2763891827 0652867497 0876863381 2636396121 6307882645 8491600680 3871778276 0040389872 6231355432 2164233204 7544925006 5639193595 8727311757 5376094730 7908271628 5221894863 5515567010 8773853748 4897209177 7030783459 0343071992 4882485079 6935367429
• v= 36 9240661841 4586312659 1051107496 0924314406 2241890829 7284325549 9559769606 6652882986 8811967615 9355723520 6574654944 5427227448 8169438092 7280807718 5613466761 8806299931 6649006474 5285242720 9277093690 1586678684 2102104041 1047729807 0907441272 6042202339 3313280474 6928384221 7497250973 9457387935 1444280192 6020757855 4894118437 3652286056 1552791848 6843552595 2772757284 1020509733 2344643502 4874018588 0601019218 2508804079 7891928845 7999741041 6216263150 5131499614 3632686411 7378220690 3351866997 1979279443 5686922710 2760728838 9098077011 3829005527 2131123204 1389735280 8762300808 6512722988 1678066953 2711000244 8226041660 9990110848 8705000765 2782944916 7832659973 8445703568 8809128915 3336119557 8907286124 2038936433 3997434752 5438197088 9552888669 1934559785 6125602735 0572950615 6048027396 5181990076 9588814379 8447682340 7479832141 7917983905

We also need to calculate d = floor(c₄·v/F + 0.5) = 30 5266877812 0545420315 6855236059 4447955581 8949516269 0055604798 9085847085 6243812141 6909988521 8527274135 8721857181 4342136210 0892102062 0801455672 0686905351 3623313048 1116304650 2460715797 1912109389 1890545197 3467014847 8321768089 4984918415 7215165843 8855090472 4165236160 6005393478 4273044870 8964118450 1928878432 6477303519 6343723040 8241088643 3669748747 6526695245 8239120249 9043181100 2252601950 8259901495 7263691501 1347138438 3312351632 3022784818 4797846634 6469979521 0871257308 6409240841 9000853271 4232888577 2876797665 5614764230 6722606134 5864340868 0954601728 2954472938 8446547193 8100108254 4185857066 6268524928 8678432514 2493145142 7000733847 6891162036 7917656600 2731635715 6335786510 8376991414 9199183129 1649939770 7292294705 9253422184 4300446837 5632145052 4006178400 5840327462 5048589665 7024382453 2928144820 8740217938 0842447120 8610496663 8523751460 3641471260 3764802962 3470465129 0156185347 2000789792 7944099702 5271474285 8635327570 0425460732 5939950503 8013596670 0279748369 3009229492 6368801429 8129524458 9819596592 0567896666 3854855794 9332232735 3003924936 6319039824 4426412335 3583268307 3217948861 2747236515 9354686213 4783051863 6256379462 7321151972 3083023804 9348047097 6815600011 9919329410 6917897822 1242089624 0067732409 8928903721 6478491833 3228633262 5924189883 2840822085 9495698925 3127377998 9795418746 9158785249 2735047642 8772291007 6979967588 3719951265 5937357746 2295614092 1833751917 6485364076 9413255228 7308979358 4115829071 9740081064 5173616703 4844911012 0794990767 4112311702 0410389444

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₁= +36 9240661841 4586312659 1051107496 0924314406 2241890829 7284325549 9559769606 6652882986 8811967615 9355723520 6574654944 5427227448 8169438092 7280807718 5613466761 8806299931 6649006474 5285242720 9277093690 1586678684 2102104041 1047729807 0907441272 6042202339 3313280474 6928384221 7497250973 9457387935 1444280192 6020757855 4894118437 3652286056 1552791848 6843552595 2772757284 1020509733 2344643502 4874018588 0601019218 2508804079 7891928845 7999741041 6216263150 5131499614 3632686411 7378220690 3351866997 1979279443 5686922710 2760728838 9098077011 3829005527 2131123204 1389735280 8762300808 6512722988 1678066953 2711000244 8226041660 9990110848 8705000765 2782944916 7832659973 8445703568 8809128915 3336119557 8907286124 2038936433 3997434752 5438197088 9552888669 1934559785 6125602735 0572950615 6048027396 5181990076 9588814379 8447682340 7479832141 7917983905
• z₂= -48 2108892460 3219066457 7566342506 3137473195 0757386492 4515059006 0199687023 4249201048 7561088393 4393544333 8460111767 6033829031 8343914408 9744454617 8192604010 0642687242 0066222285 4188850370 2582518205 5578853930 1993227907 7079470703 9218121350 6964647556 7843880979 3075792595 0481869611 1961912696 5825641372 3017761497 4206757898 5744056755 0650608759 4107814665 3644700347 7744501718 7090233186 3415286018 4766265435 7223942229 1325035003 7060350125 2696239659 1764936882 3589733993 4339780096 5244783175 2230760542 1484477732 5664424749 2683253036 6567229784 4073738962 5629655588 2521269561 2520875121 9892145985 3424780279 1610696420 2686848406 5594128499 0251292123 7318103548 7679251126 3340794729 9400511082 4538041464 1990181626 8145615440 9075495399 4900097251 6789627545 2695875162 5121393037 0072327360 4513733408 3663781141 8762753041 3379081766 0496739879 8154488210 4354234023 7676089588 5870962106 8493470071 1073600970 5759724382 0079609485 4079153385 7553422106 5989400476 1088812441 1481385697 5937760029 7378660545 6529064406 7887700752 3416858741 3271216120 2694049231 7445398175 2984848151 1435083404 5650850615 8070332456 3939284661 2368343457 9470140374 5162348232 8544598338 9050234612 8841537547 9363522980 1194253992 9734396628 9169805724 8537530104 9830770900 9865501889 8087333304 0431758368 2543958976 0138956903 2587579617 7473617055 9062276237 7425149499 0433365145 6429487089 0809486255 3497985004 5699100185 3625951412 4279067933 7192079292 2196097047 4841740472 4061649438 4409945954 9114178200 3581718411 7585814243 4640598081 1967042665
• z₃= +1145 9820856994 8290761564 1898787014 7038087163 1218263387 1715025469 4176616860 9479258190 8502301202 2818864942 9891992227 8596587057 4291038620 8254035683 2868492204 5779341734 4596099999 6147186611 4580718879 9032974895 4344239779 8218410636 5230004908 1231500562 1699521584 9372555966 8445947324 4670227987 9114006882 1010637565 9983946476 2910281735 2782651688 3042042210 9172279223 5773248629 3852663458 6324230958 9273421566 5030291688 8520993968 6735516422 9294992503 7544793892 4274816283 8266511617 7582936391 7062147009 3452830976 7194998451 1085328351 9702550898 0346218150 3600298308 5121175254 5872090752 7588161898 4014207809 6381721029 7904434344 0143090201 3237770935 1125729965 7582785017 9545583547 4707732509 6758314893 8249896388 3892598685 9375036730 6536952844 9129185687 8556999217 7120265696 9290961626 5925208049 4540880793 2129702796 6690063031 8942308964 7241786222 2693007378 9678225546 6501868903 9575923125 1195118945 1491474035 6182017255 0590306002 9605229357 9847259559 8843673492 2300556310 5043866987 5523651852 7569777735 8135883448 0255087803 6259323958 3810494496 4431096082 1482694630 4517953651 2871439352 9603761731 8936694661 2588717694 1608939280 2672119706 0058835759 9593802284 7458133421 3684240521 6580982527 5509144973 1695441501 3475617352 5073759497 3906487172 9185010899 9237422186 0665453293 4306330241 4006559902 9744317932 1458594604 6232579295 4627906109 1500966394 8004399130 1258400459 1446676684 2859913577 9748007265 9836450513 8106995223 2661337557 9477292256 2520114572 9455452388 9431505695 2627460702 7811784515 9609666804 0396885763 1244258232 1061805241 1893155587 8269171265 6663951740 2905153027 1855136547 3435692949 8107939219 2583141568 5184867527 6336530349 6449079488 0293341151 4565951224 8282734841 7463100104 4524914926 4214264628 7170665170 8974117883 5877004757 0227946764 4994026583 9655556284 1608886708 5022701844 7427390251 0630140496 6059994327 7978067717 9756835410 4571543007 5163597213 2223780050 5593899573 4571662161 9290709937 1673152009 9081781848 6778026825 1842424276 6974675897 7352782814 7258612906 5422890945 1523888241 6302721532 1999563822 1543585966 2431938370 9523181195 8086861451 3257878092 2120725278 9982283961 7380803721 9813427847 2699449537 2524261674 0588266856 6062530918 4028092842 1776683971 4020095206 5041055874 2070989122 9674309905 6239833693 3311436347 3149795441 3479836355 4512518694 8438971288 1807558822 8377546792 5576274232 5197514004 2978391649
• z₄= -30 5266877812 0545420315 6855236059 4447955581 8949516269 0055604798 9085847085 6243812141 6909988521 8527274135 8721857181 4342136210 0892102062 0801455672 0686905351 3623313048 1116304650 2460715797 1912109389 1890545197 3467014847 8321768089 4984918415 7215165843 8855090472 4165236160 6005393478 4273044870 8964118450 1928878432 6477303519 6343723040 8241088643 3669748747 6526695245 8239120249 9043181100 2252601950 8259901495 7263691501 1347138438 3312351632 3022784818 4797846634 6469979521 0871257308 6409240841 9000853271 4232888577 2876797665 5614764230 6722606134 5864340868 0954601728 2954472938 8446547193 8100108254 4185857066 6268524928 8678432514 2493145142 7000733847 6891162036 7917656600 2731635715 6335786510 8376991414 9199183129 1649939770 7292294705 9253422184 4300446837 5632145052 4006178400 5840327462 5048589665 7024382453 2928144820 8740217938 0842447120 8610496663 8523751460 3641471260 3764802962 3470465129 0156185347 2000789792 7944099702 5271474285 8635327570 0425460732 5939950503 8013596670 0279748369 3009229492 6368801429 8129524458 9819596592 0567896666 3854855794 9332232735 3003924936 6319039824 4426412335 3583268307 3217948861 2747236515 9354686213 4783051863 6256379462 7321151972 3083023804 9348047097 6815600011 9919329410 6917897822 1242089624 0067732409 8928903721 6478491833 3228633262 5924189883 2840822085 9495698925 3127377998 9795418746 9158785249 2735047642 8772291007 6979967588 3719951265 5937357746 2295614092 1833751917 6485364076 9413255228 7308979358 4115829071 9740081064 5173616703 4844911012 0794990767 4112311702 0410389444

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.