Primality Certificate for (31^5581-1)/30

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

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

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

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

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 = 29 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₁= 159739 9194272074 5933355043 7459196864 8926128511 8301190396 6423400681 8014780842 5258022247 9012787803 2982413897 6504605788 6807139701 5407512100 4630149254 1170648367 8732298292 9278890067 7514800957 2145362188 0414499083 5457875983 3527226287 8342365160 0905438176 1156658073 4648084442 2300714060 6177847286 4164586203 1599455274 7627368387 8140023931 4208347448 2410046760 6668853733 0876989840 0029612037 4813725519 2781975545 5947170785 9802206438 3958610670 5023648888 9279962768 0062437512 4262379834 2248803027 3454339796 3423848507 5003470027 4299422725 4367725376 3281895182 5316995826 0973629955 9795813956 7714683545 8157286587 5433565320 2961868768 0896909301 4079111580 1367599842 3104441902 8311490518 6399548080 2052666726 0614955777 4827564686 8503678508 7709899582 3755189210 8075907153 0693771986 2851764176 4030338084 6755654615 0846171525 5585928758 7468319044 3397615999 0294985638 6180311467 5214139154 4081676566 9606021598 3216107698 4679864507 3626943907 0641637152 3013300019 3512625114 7024906355 1001182412 2385253904 1282349858 2024673178 4796102517 9313225822 3000945112 1001945207 4789899401 6495758055 6253320932 5894240526 1059410275 9260824923 1379591750 5997736105 6769442451 2366529498 8599996297 0831446647 8973212792 0015784841 4648152821 8157092246 1338116783 7225507938 5909460252 0776061514 5238901809 4989374973 0039026412 8328242793 7568717124 1927541668 5430855156 5744476950 4737937024 1588174352 9238570355 7764130330 5916710442 8270261583 5783319305 1493896815 5226032515 9353851548 4786482320 8372228937 1608148639 1421274237 5531534547 6309304450 9521446417 6767264190 2555794163 2161264172 7080603949 2979311475 5069627572 7873311002 1283299239 7370557725 7952454939 7536844794 0638831583 6090583976 6232411894 5748630319 6636759908 5180091953 0384350763 4786109138 5786111717 6747054897 0950158134 7452132773 9876220904 3529255814 7885465392 3497668581 5000821598 2762430405 2491697200 9912293853 6977901725 1678416673 7239792022 4892184797 9740278626 8181465831 6115486296 0963185371 5975069420 8452420982 4719245973 5759896099 6396283174 9606889813 2634671726 5276907355 3842474043 5179970353 0606106835 6754458997 1842794280 5376893328 6894869118 9717476802 3765363833 7382891492 6237555443 5391807531 6311611880 0766468669 2476317688 2359442848 3364149464 0846710522 6204389350 9934948954 6969278606 2659355624 7283319858 1556692299 1001605693 9566668274 8437357359 4805178838 5740593572 8713582672 2885491837 7916074493 1753442284 8636767022 6179230051 2119532256 1514952026 1493535630 2624089974 3319582112 8757384677 4863815129 5777840934 8748569833 4011349515 3471656071 5719651635 5166951538 5071244558 2506138461 0409143515 5724415686 0152813544 8285072783 7983522021 5955736581 9454330633 1054575975 6179175815 7202963791 1436600833
• c₂= 140507 5114575954 9694624449 5899220750 0216858544 7525435054 8337870319 2348827159 7685769636 4548109186 1919144293 1441858086 3900041874 4862769293 1572677262 6794017754 2887894951 1308182655 6305955917 4718334591 3238795696 6475602116 9886141424 4673737246 6514170776 7870893053 5768795450 2344183216 2750635065 5159963835 8092086781 3210094841 5341040228 2720679687 2084666719 0432326197 4414162814 6021787530 0827038232 7473328376 8263669380 5652736281 7902559360 9192567925 7222872860 9843442092 8845441144 2558385089 7096984538 6803972649 3978994925 0069407514 0949590159 7378519354 0389788531 9053984389 9754523935 3451324561 9747935201 3097465815 5314068231 7371325355 2886150232 1867714265 1297657510 7214596631 3620359715 5469144483 8938079438 9629917805 3121511264 4950326103 9874102531 3702408057 9535426568 8132143754 5023773869 5770892250 7312742210 2394055609 4493798854 4666424834 5311791013 9579558492 0347954677 0375220826 4468592712 4877591600 9636053207 5659948367 2944952308 8294834616 8094946029 0928617628 7050716934 5275681745 5756507770 2775084354 4766535827 1575923171 7076189394 4478262793 8559786651 7545804104 8315469310 6877269218 4475923816 1469013250 5052128697 1661124894 3931821794 3510898232 2838458725 4591774247 0137516588 3873648340 9316856115 4586507023 9062056263 5851266846 6270466701 1792348721 7865505617 7464077353 5751820731 1539596342 6910538255 2139954924 4012501488 4654661024 2701543401 3025719008 1642786202 0459061045 4591688749 8808679819 8472041662 7565355076 9480259127 9137846883 6299530703 8797182613 5228457290 6248556219 0636583576 1973765721 1035070031 2832968907 9488994139 6790395995 8363295664 5023710904 5248979780 5581508573 4073564536 1418271064 2569126150 7318751853 5396356883 1338225941 2180300285 2302400128 3748063566 2535602696 3730366571 8640273212 0646073199 5629049517 5625938589 2502131053 5715580017 7842346468 8828292345 1109054155 1749830645 3946130566 9228898760 5222230662 3643145306 9835217465 9915772200 1201194122 7338344231 3041926629 4677459293 0496814055 9796716996 0581477333 1359901835 2412085041 4361051814 7874543313 1963692228 5204853538 3009910277 5124087081 7028861093 2575454822 6856833734 2427686165 3841028007 1425060323 7765676702 7673008667 9853794112 2638579743 0309880321 8173688889 1106353331 2796867878 9634942317 4350665950 8273640793 7328267679 0474138856 4687292292 0602991517 7921662901 0803667656 6148585744 8918229163 3248276613 2721523897 0380053426 4071713446 4635459363 4343972046 3574137955 2058888302 2808101737 4467411992 2462300642 6463550407 6379091073 2157685631 3565190652 9073550553 3342582271 2645568973 8706868868 9468633218 9220579253 0115841313 2156710816 0823659378 0663948719 3229707428 4984865455 3426237624 6247776860 0097164538 5492764685 3033445474 6829731998 8590719629
• c₃= 83275 6704602372 9572025435 2665081949 0827003834 7818769028 4448379669 1430407514 4889894860 6497816628 6563741763 3388249314 2721883966 1194883610 7820396742 8226459811 2048282364 7951152794 2829748275 7236679301 1267383165 7644605531 5122006689 0172718675 2904776008 2376421500 1167098207 8288257852 7017699931 8696008590 2202368310 6497717100 8860514023 0353368303 2612718158 0106193726 8471049252 6678728855 9792980384 7222848781 8491774383 1138224680 4118407932 9772588028 1045692909 6565252749 8885172421 2732886394 5917093208 5981019566 5804533087 2922070798 7134955762 5791691742 5858635025 3228085775 3841170100 6332557211 2728483736 0433663208 2700966054 2874571935 5899276288 6210761785 0089054232 4999314902 8361133902 5533693759 0075841208
• c₄= 3 5577555384 3657894214 9384800060 8289718917 3069026634 4298266075 8353653019 2607362496 4564012984 5961327079 4305535995 0754055289 5961195909 6615945539 2234838038 0407266963 9690982339 0762796189 5763200257 8621003639 2540104624 9775318913 0729698010 2520215815 6451489448 5206460388 0723875121 2703604819 9909813463 6184507886 1901865424 0006944737 8708125032 3029922928 5476486840 9800798746 3480103510 1961167148 0281497232 9360411225 4133537593 1720515367 7482633744 0920255231 7366859403 8009859334 3912541344 1215322090 5589263163 3347231969 1855417918 7593905824 0655271870 4891815881 2303593408 6222051833 2483213153 8435657961 8445325839 8248082127 5780381294 2894546806 9305378390 3818228758 8123932470 9719362257 1185194639 5537752760 8175597688 2865077435 2442813200 3694336285 3761072608 2881506264 9950678284 5604757888 4267867565 0269129105 3953058852 1576617171 3040191213 0317786079 3227162961 2411952052 0372003798 0957656471 6575502340 6084630092 4297155737 9531373772 5124611990 6771857155 9043182871 9401023354 4999533571 7513869444 6308094949 6859947795 6209442496 8894868909 0607091564 8846884180 5756826535 8004327723 8992135584 7212974320 6883462247 9633481152 7688673861 6720346275 8913432483 4651457642 6027806147 6433102077 3290573014 8140043823 6417473220 7336238884 1740866425 9487659111 0535031440 3832981731 6928907699 9108511066 6302323288 1909466362 3322772651 9139484777 6630880263 4392949677 3905582099 4502354424 8466511017 1206694363 8166951999 5934088593 7741237183 2545668957 8754354439 0727634264 1711054834 3783975792 6157572112 2194387887 9581637386 9256464803 5896781998 7430170925 4695156404 2963164273 8820473209 1372012134 6573487483 5505168390 9096669771 2782628571 4849631323 3735066480 3869989439 6065712515 9254689309 0254931303 3202580692 1038201122 0456550537 8639549180 4584518468 8614700724 6037362070 9600894666 1913474906 1928959922 6200905776 9202752300 3255092956 8029754635 2738538047 7559193924 1326708589 2510703369 1212061377 0884665476 0361791372 5151363130 1333051182 1797694669 9755870198 6236396131 5412356361 1945884400 8140691807 1668997660 9068555102 4777838616 8628765902 0508685852 6566886502 2269824713 3467736931 8636588227 3499715549 3363860516 5482257212 0933442923 8184850878 4898187028 6771624337 3166641419 0319291831 3590879690 1662180974 2472570495 1061780063 3784437773 5419856249 6963952199 0927356817 2710365312 4597718140 8733476282 8565785520 3659783407 7780001952 3439961638 2442082851 5142779314 4731214973 3986793850 6494019218 6381780960 1346095038 1944434888 0634660692 9102620857 1990656740 5302307175 9474562362 7234407884 6655450752 7426427512 3017054961 7378926098 5360339602 0905619849 5198622055 2349448485 2161990255 9867552710 2464260167 7295462110 4135358446 1518265693 0968515456 5807548002 7028985442 5604127261 7270094389 5856801884 9621345183 3492184086 3132579548 1687192163 5882996043 9746799170 6136043512 0247992026 7668910803 9057921249 5574998036 3447099187 8024416446 8321952036 8889366122 5799660656 8280726740 9959619006 4383491215 2381247949 7099371009 2137729175 5437266038 0837588411 7648384161 7468086883 6847032882 1243819039 9181059579 5415933981 6795293986 6166929258 1399973719 5245488081 4579681682 5972983220 2027104232 4528730436 5416686596 9189503225 3779635824 4268551646 0884016170 8109939090 7714631615 1476031090 9747654637 9811501054 3342186020 2946401490 1009214918 9891410572 5381938002 4116560279 0124308531 6410671888 6661524270 2872842866 3174935781 9520529204 3942595885 0279566633 3737801997 8967372138 3595706509

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 ≡ 13 (mod 64)
• Q(1) is not a perfect square: it is ≡ 2 (mod 65)
• Q(2) is not a perfect square: it is ≡ 21 (mod 64)
• Q(3) is not a perfect square: it is ≡ 34 (mod 63)
• Q(4) is not a perfect square: it is ≡ 29 (mod 64)
• Q(5) is not a perfect square: it is ≡ 42 (mod 63)

Continued Fraction

We approximate c₁/F by a continued fraction u/v such that v is maximal while remaining less than F² / N^1/2 = 2 2650089048 6401088585 9940374805 7569502390 8821056831 7731563237 7241896087 7640808958 8538020615 4013172299 3234732696 7340504890 4238217456 9304889023 2547411107 4824118530 5612575571 9586746380 5977942856 5313842873 8068313950 4453613244 7360731470 8414002453 3084587049 1435886052 6894305128 1575919463 4403763275 8500359911 0715877527 3666536504 4683130440 5147239484 2074954787 9660438448 8901886042 0425076286 0891263370 3025046900 0817204963 0037287172 6580205066 2073764902 9839638178 2599817342 6004118318 9045677903 9080266599 8263348311 2384022028 8241695381 1264464245 5321624271 2202078458 2971431194 1322505869 4538896124 3960935267 0748792619 0361063727 1453271157 4984336204 6631925505 5367970078 4083674403 2258795055 9972875202 1488410780 3063033033 6799925440 8032998253 8805409637 1164097617 4343951884 6433659919 8414716843 3062723210 1688973909 0941627995 7822774224 6361803750 4531371572 8036137382 0298221516 1504973027 4646946618 9955894051 2137071615 9814984158 2172455543 3499210131 1201899801.

With those constraints, the unique continued fraction is: {0, 2, 1, 2, 13, 1, 4, 1, 7, 4, 1, 1, 2, 1, 5, 1, 2, 2, 9, 9, 2, 24, 6, 3, 1, 16, 1, 9, 33, 2, 2, 4, 3, 8, 2, 1, 2, 5, 1, 5, 5, 2, 3, 1, 1, 6, 2, 17, 9, 1, 1, 39, 1, 16, 8, 7, 3, 1, 9, 1, 3, 2, 3, 4, 1, 1, 10, 1, 5, 1, 3, 21, 2, 103, 1, 1, 1, 3, 1, 1699, 46, 1, 1, 30, 74, 5, 1, 1, 2, 29, 1, 1, 4, 1, 1, 1, 5, 9, 3, 22, 1, 1, 1, 3, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 3, 8, 4, 1, 21, 1, 2, 1, 1, 1, 1, 10, 7, 3, 3, 1, 1, 1, 90, 3, 1, 8, 4, 1, 3, 1, 1, 3, 2, 2, 2, 1, 4, 4, 2, 2, 1, 5, 1, 4, 6, 5, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 28, 2, 3, 7, 3, 2, 2, 16, 1, 1, 17, 1, 1, 23, 1, 2, 1, 2, 1, 1, 11, 15, 3, 6, 13, 1, 7, 1, 1, 6, 2, 1, 33, 124, 2, 2, 2, 70, 1, 13, 2, 1, 7, 1, 2, 10, 1, 3, 2, 1, 1, 1, 3, 3, 1, 2, 1, 3, 1, 1, 1, 5, 1, 1, 9, 2, 1, 2, 2, 3, 3, 2, 3, 1, 2, 1, 3, 1, 1, 2, 2, 7, 4, 2, 1, 1, 5, 12, 1, 1, 1, 6, 1, 9, 4, 1, 5, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 5, 3, 1, 1, 1, 1, 21, 1, 1, 3, 1, 14, 4, 69, 5, 19, 1, 3, 98, 3, 231, 8, 2, 1, 2, 70, 1, 6, 8, 1, 1, 3, 15, 1, 1, 2, 288, 1, 2, 162, 1, 1, 2, 2, 13, 1, 6, 2, 6, 1, 4, 2, 5, 16, 1, 10, 1, 2, 1, 28, 4, 2, 12, 1, 3, 45, 1, 10, 2, 27, 1, 2, 5, 4, 225, 1, 5, 1, 1, 4, 6, 1, 3, 172, 1, 1, 1, 1, 3, 6, 1, 7, 3, 1, 53, 2, 1, 7, 1, 6, 3, 2, 4, 1, 1, 2, 9, 2, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 15, 1, 3, 2, 2, 10, 1, 8, 2, 7, 1, 12, 1, 3, 3, 1, 15, 2, 1, 3, 1, 1, 2, 2, 15, 1, 32, 1, 1, 1, 6, 1, 1, 1, 1, 2, 1, 3, 7, 2, 1, 14, 2, 1, 13, 1, 6, 8, 4, 7, 3, 1, 2, 38, 5, 2, 66, 1, 5, 7, 1, 5, 1, 1, 9, 2, 1, 18, 10, 6, 1, 49, 3, 5, 1, 1, 1, 5, 7, 42, 1, 4, 2, 13, 4, 1, 12, 5, 1, 1, 3, 48, 1, 1, 1, 18, 89, 2, 1, 13, 3, 1, 1, 1, 1, 3, 1, 2, 3, 3, 51, 1, 1, 8, 1, 6, 5, 1, 1, 1, 7, 16, 1, 2, 1, 1, 1, 1, 3, 9, 1, 1, 1, 1, 14, 2, 3, 1, 1, 2, 301, 1, 1, 3, 1, 3, 4, 1, 3, 1, 1, 16, 1, 26, 3, 2, 17, 7, 1, 15, 6, 1, 14, 1, 9, 2, 1, 1, 1, 2, 64, 3, 3, 1, 3, 3, 1, 2, 5, 1, 2, 1, 2, 26, 1, 1, 1, 1, 2, 2, 5, 8, 1, 4, 1, 1, 5, 1, 7, 7, 1, 3, 5, 1, 1, 7, 2, 4, 1, 1, 2, 5, 1, 2, 2, 1, 1, 1, 2, 1, 2, 28, 2, 4, 1, 19, 3, 34, 1, 56, 8, 5, 1, 2, 1, 2, 1, 7, 4, 1, 4, 2, 1, 1, 3, 16, 3, 1, 24, 1, 1, 41, 2, 1, 2, 5, 2, 6, 1, 1, 2, 2, 6, 5, 1, 6, 1, 3, 1, 3, 3, 11, 5, 2, 2, 23, 2, 2, 1, 1, 17, 3, 5, 3, 4, 6, 3, 2, 1, 3, 8, 8, 17, 1, 1, 6, 1, 20, 1, 1, 1, 16, 1, 2, 5, 4, 1, 3, 1, 12, 13, 3, 2, 1, 3, 1, 1, 1, 1, 14, 90, 2, 1, 1, 2, 111, 1, 7, 18, 2, 2, 4, 1, 2, 2, 1, 8, 5, 1, 1, 2, 2, 1, 2, 1, 1, 7, 1, 5, 17, 2, 1, 1, 13, 2, 3, 7, 2, 13, 1, 1, 1, 4, 13, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 4, 1, 2, 1, 1, 4, 1, 1, 1, 12, 7, 1, 4, 2, 8, 2, 9, 2, 4, 14, 1, 2, 6, 12, 12, 1, 27, 1, 1, 1, 7, 1, 6, 1, 123, 3, 1, 1, 6, 4, 7, 1, 2, 2, 7, 1, 3, 22, 3, 3, 1, 2, 8, 1, 7, 4, 1, 4, 3, 10, 1, 1, 5, 1, 2, 2, 1, 8, 2, 1, 50, 3, 2, 1, 2, 2, 1, 4, 16, 1, 1, 5, 1, 6, 13, 61, 18, 1, 1, 3, 1, 1, 1, 21, 1, 29, 4, 3, 2, 1, 6, 36, 1, 1, 2, 1, 5, 1, 3, 6, 7, 2, 2, 2, 5, 1, 8, 1, 3, 15, 4, 42, 1, 1, 2, 3, 1, 1, 1, 9, 146, 3, 21, 2, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 3, 1, 12, 1, 4, 1, 1, 6, 1, 2, 1, 1, 10, 18, 1, 2, 4, 1, 7, 1, 1, 3, 3, 1, 6, 1, 8, 1, 1, 4, 1, 1, 2, 2, 2, 2, 7, 2, 3, 3, 5, 2, 23, 8, 7, 2, 2, 5, 19, 1, 1, 13, 2, 2, 27, 5, 1, 128, 3, 1, 1, 1, 20, 8, 14, 1, 17, 5, 4, 3, 3, 6, 4, 1, 9, 1, 151, 11, 1, 2, 8, 1, 4, 1, 2, 1, 6, 1, 2, 3, 1, 6, 1, 1, 3, 1, 3, 1, 20, 1, 99, 2, 3, 19, 1, 2, 1, 2, 3, 3, 11, 1, 1, 4, 3, 2, 1, 4, 2, 1, 14, 1, 5, 1, 4, 1, 1, 9, 4, 3, 2, 1, 6, 2, 12, 4, 1, 1, 1, 4, 4, 1, 3, 2, 4, 1, 1, 1, 8, 1, 2, 2, 7, 2, 1, 5, 6, 3, 2, 6, 1, 235, 1, 15, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 7, 1, 4, 1, 5, 1, 1, 2, 2, 5, 3, 3, 1, 35, 4, 25, 3, 1, 3, 1, 7, 6, 2, 1, 3, 3, 1, 3, 1, 2, 4, 1, 75, 1, 1, 2, 19, 8, 7, 1, 27, 1, 2, 1, 1, 2, 1, 1, 2, 2, 10, 2, 1, 1, 5, 36, 3, 7, 1, 24, 3, 3, 12, 2, 1, 1, 6, 1, 1, 2, 4, 1, 6, 3, 1, 8, 5, 2, 1, 2, 8, 2, 6, 1, 16, 1, 3, 1, 1, 1, 1, 2, 1, 8, 5, 10, 5, 1, 10, 1, 26, 1, 3, 1, 2, 11, 9, 57, 1, 1, 3, 1, 9, 1, 14, 1, 21, 1, 1, 2, 6, 1, 5, 6, 1, 2, 1, 1, 2, 1, 31, 1, 1, 2, 4, 3, 1, 2, 12, 126, 6, 3, 1, 4, 1, 1, 1, 12, 15, 6, 1, 10, 42, 5, 2, 1, 2, 7, 11, 1, 1, 2, 1, 7, 2, 11, 1, 1, 1, 1, 6, 2, 3, 3, 1, 3, 3, 1, 2, 1, 5, 1, 11, 1, 2, 2, 4, 1, 4, 1, 5, 2, 4, 15, 1, 1, 7, 1, 3, 3, 3, 1, 2, 1, 1, 1, 3, 2, 10, 2, 13, 1, 1, 15, 1, 10, 2, 6, 1, 30, 31, 1, 1, 15, 59, 1, 1, 1, 2, 39, 1, 1, 1, 1, 4, 3, 22, 1, 7, 1, 3, 3, 1, 4, 1, 23, 2, 2, 2, 1, 4, 2, 6, 3, 4, 5, 2, 13, 3, 1, 1, 1, 1, 18, 11, 1, 1, 2, 14, 3, 10, 1, 2, 3, 1, 1, 2, 1, 2, 1, 2, 1, 6, 1, 1, 2, 5, 2, 5, 2, 1, 1, 2, 4, 1, 4, 2, 6, 2, 1, 1, 1, 1, 24, 16, 3, 1, 1, 1, 2, 106, 1, 3, 1, 48, 2, 7, 1, 6, 1, 1, 3, 2, 1, 39, 174, 1, 17, 14, 1, 1, 2, 1, 2468, 1, 3, 1, 1, 1, 3, 2, 21, 2, 1, 2, 4, 5, 1, 3, 9, 7, 1, 2, 1, 3, 38, 1, 3, 1, 17, 1, 1, 1, 3, 5, 11, 3, 4, 1, 1, 1, 1, 1, 2, 3, 1, 12, 17, 2, 1, 2, 1, 1, 2, 1, 1, 49, 1, 5, 2, 31, 1, 2, 1, 2, 5, 1, 1, 1, 1, 5, 1, 2, 6, 11, 1, 1, 9, 5, 2, 1, 1, 1, 2, 2, 2421, 2, 5, 16, 1, 5, 14, 6, 1, 1, 6, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 33, 1, 5, 1, 5, 6, 4, 4, 1, 1, 2, 5, 1, 4, 1, 4, 3, 1, 2, 2, 8, 5, 1, 1, 8, 6, 1, 4, 2, 1, 2, 1, 12, 3, 2, 1, 1, 2, 1, 2, 2, 1, 14, 2, 20, 2, 1, 1, 6, 5, 235, 3, 1, 2, 1, 5, 1, 1, 1, 27, 4, 1, 3, 3, 1, 1, 1, 1, 14, 10, 1, 16, 1, 1, 2, 3, 23, 1, 1, 1, 149, 3, 2, 2, 1, 3, 1, 3, 3, 2, 2, 1, 27, 6, 22, 1, 2, 1, 3, 5, 1, 1, 4, 4, 1, 1, 1, 2, 10, 1, 1, 3, 4, 10, 4, 4, 1, 308, 1, 1, 1, 1, 1, 1, 4, 10, 2, 6, 17, 1, 2, 2, 1, 4, 3, 74, 1, 3, 1, 29, 48, 28, 2, 1, 4, 2, 5, 1, 1, 1, 1, 1, 1, 4, 5, 2, 3, 1, 6, 1, 9, 25, 5, 1, 6, 1, 2, 1, 6, 4, 1, 2, 21, 8, 12, 1, 7, 1, 2, 2, 1, 1, 11, 2, 29, 2, 3, 4, 1, 7, 5, 4, 3, 7, 1, 2, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 11, 1, 1, 1, 2, 12, 1, 1, 2, 1, 45, 1, 4, 2, 1, 1, 47, 2, 3, 1, 2, 2, 18, 1, 1, 13, 2, 1, 3, 2, 298, 2, 3, 3, 3, 1, 1, 11, 52, 8, 7, 1, 4, 3, 4, 18, 2, 11}, giving these values for u and v:

• u=4151629701 4602049652 8706140043 2929331238 8224928129 3021511441 9435835481 1867899981 3306220303 5400798568 8266511042 7622501208 0696479034 8263209333 4739187733 5756939442 7236099183 2053963233 4482957824 1702479799 3522086755 2786434832 1268286021 8523935345 2459791527 9679877200 0941002171 2105845186 6999970355 3017938355 7499225204 9694590675 5586837625 7050546983 4698714434 7587883313 6106162012 1595192999 9715662828 5778625542 4123274384 8080598864 8235337477 9268891075 2196749721 6208870490 6336079500 6802989517 2026307635 4980238038 0102708941 2664363839 7618871417 0967646590 2626875724 9976544832 4962983670 2158528950 7922230166 7849559618 0099061942 3001860784 1420479204 3474746254 5973620255 2163501264 5448123357 1024613073 4636543610 4077511754 9775404106 7874002271 5920421915 3807698598 1366352150 2259593891 7304199485 1644431977 7950976146 1075828554 4123686259 6639876189 2815707224 4299051085 8878559960 2803139375 5634629129 8188464113 5050951129 0893034172 7554922875 7030404576 7753438128
• v= 1 1103582270 0994917670 9789727946 6565063459 2721892666 7518185355 8947129530 6214271498 0017019686 9665068060 2938362357 9914803045 1487586149 0686901481 5365965024 8043798506 7453610016 7315152254 5734565462 9967646953 8553143369 5026320147 6328963903 1559919491 2725913422 0807514747 6875509670 9594325359 2805919725 0558878311 5359042762 7864799172 1320624098 6514682546 5008607631 3592301120 5921693391 4130231715 7670974579 1535943251 0730172233 0608986336 5854966213 2701726656 3187752780 4745689574 9046820996 7386293953 8396621649 6890693760 7798254749 9939342316 0638973725 8406741643 1729435556 7520487907 9363993450 3703522796 4482545095 2740677224 6225100774 0575227713 2198233999 2449358632 0095711298 2454712974 4393192037 5507093221 7404850136 8293522630 3408777776 9166739274 4673432788 9291316741 0736369109 5351608308 9160744456 1797581939 0231527757 4049615114 5147394839 9570916854 8811078879 6724630339 8045736499 4000428754 1342767643 4332796568 5530029247 4693712644 5298806479 0017040322 0898478729

We also need to calculate d = floor(c₄·v/F + 0.5) = 92465 8258052938 8203625142 8351665224 8586030202 6960590582 4173825140 1243088985 1943177595 7689022209 3412231241 3374313483 1540401666 1302817105 1631111976 7137803607 3674728856 6186275517 6707145786 8439330886 2435690704 4052456191 9378343821 2777122673 2903711512 9996374287 7672486823 3504025718 2900702496 9507066866 7762764493 5463484678 6147383917 3442605712 9151892861 7941975696 7952515710 1795195270 9094372841 8575624002 2788256727 2895570869 1556016032 9090856682 5339850228 7324722354 7876903229 8988559975 6445442913 6424784197 3697106369 9325878265 4112686932 2500108054 2145976782 6747936467 2759772477 9685993832 6162249530 5958945635 4346927065 6341650219 1285109033 2354166928 7884221974 7337697039 0063259795 6415580233 4149383399 3817595796 7630970900 3285531360 6798559385 4937599700 7047260074 8850676022 4280789421 2519004483 1970682421 8333846590 6178381198 2264369206 0037288451 1944547719 9151442243 7263592349 8731309633 5151147127 9948806635 4446894973 5234658345 0148807236 1747314700 3590792191 4433562095 5354685231 3847768704 1336500305 0667231692 7724180264 4210311681 4670792081 9845396322 0213303181 1456236244 8202702134 9156064764 4718100193 3938766554 0250060456 7323954698 8134870588 8570575570 6006813793 2141810169 7304482857 5791440313 8621391132 9738451854 2485172938 2070177355 8091896942 5059331396 9634879807 5801357849 7482074284 2178990841 9802783395 3600175760 3882344901 0712732587 1659115953 9728654591 3949680530 6658971324 0280704053 3153762637 3208309785 0957646842 7619022184 4066756988 2643089409 5932486216 9256481608 7228346070 4901339350 6545284657 4614357692 0684032711 0339330092 3241425101 5563844056 9616693922 9641505306 9160971360 9123244064 6398089664 9618728457 7229028974 6413184268 4325586864 6535620602

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 1103582270 0994917670 9789727946 6565063459 2721892666 7518185355 8947129530 6214271498 0017019686 9665068060 2938362357 9914803045 1487586149 0686901481 5365965024 8043798506 7453610016 7315152254 5734565462 9967646953 8553143369 5026320147 6328963903 1559919491 2725913422 0807514747 6875509670 9594325359 2805919725 0558878311 5359042762 7864799172 1320624098 6514682546 5008607631 3592301120 5921693391 4130231715 7670974579 1535943251 0730172233 0608986336 5854966213 2701726656 3187752780 4745689574 9046820996 7386293953 8396621649 6890693760 7798254749 9939342316 0638973725 8406741643 1729435556 7520487907 9363993450 3703522796 4482545095 2740677224 6225100774 0575227713 2198233999 2449358632 0095711298 2454712974 4393192037 5507093221 7404850136 8293522630 3408777776 9166739274 4673432788 9291316741 0736369109 5351608308 9160744456 1797581939 0231527757 4049615114 5147394839 9570916854 8811078879 6724630339 8045736499 4000428754 1342767643 4332796568 5530029247 4693712644 5298806479 0017040322 0898478729
• z₂= -155464 2617240764 2491314191 3064522171 6410397049 1518482641 5825906463 5576571763 5071591971 7819019242 6247153087 6848445940 9613295927 3960313849 5606922477 1985906510 4455709272 9253214311 8118738214 6184866403 4024770659 8126279768 3794945214 3122066967 7446260170 5643791068 3973348065 9151804575 1709458611 5229881331 6486569588 8379723990 0555950906 6025688953 4226769323 8617131417 4085264360 1367946280 0565994249 5406088907 2937589984 5264899652 1591196597 4017869659 4412508193 9495934920 2811978197 8329448000 2395744562 6263576120 5833310788 5099477893 6365013191 8864801009 2412246180 4068190472 0663902360 6424845661 9313680694 1066834045 2481379557 3347444482 6255727200 4999425613 2862997724 8919823968 3248711932 6858800011 2681631788 7444412803 5480795836 0794928272 4074274226 3424493939 9467263862 0916589645 0674997121 5388837793 4844019312 0700392097 5255023535 0543758866 5391417615 1664302752 7913728607 4562647063 2719258323 4901882529 3680150116 9816115619 6442861215 7212189016 8020465937 9338358131 7950550816 1489470030 7654193048 2991471605 6370144445 4074650164 3880314754 1871689214 2744190016 6686456609 2718959839 8051157284 8754920538 3371322933 1701098617 9182939107 5369603072 8033671201 8053023271 6546157954 8115824041 3284665750 9770513826 5176154080 1949116005 5073913221 6087702853 5005432418 1653185340 6077083697 2026195102 4759817939 5515990335 5268720460 1106935979 2505931506 2215957783 5871095547 3822797905 8466072500 7843354321 0754437793 1592102342 9983775174 1182625693 2272551786 5289708420 2543396837 6510177454 6841734368 2913110170 1325622903 7352831658 0073238090 9502123571 7676640325 5159996693 7376479933 3613022368 8946123492 4904563626 8938579224 2767231985 3597798526 3184864106 3193275458 1008461363 0324823177
• z₃= +14943 9961542458 3991764573 6770697230 0814826528 7941516908 7759023807 0875193476 2477997635 1539722851 5559887047 8763430431 7554209285 8049182377 5650241292 1578714948 6096635573 8743416701 1299123093 9023252300 5838847962 4101619432 7881197734 3353835856 9774645979 6550898064 6653507675 3885640526 9292799349 2664426557 8231893676 6426156705 0163473259 7620704859 0706273561 9858180244 6870991374 9747645930 8054626645 8794593700 3238985130 9979518610 5537830372 7987322862 9322617550 7095574632 1777581508 6086683670 4537822030 5348265711 1260320952 0892748739 4450020302 4463048874 6301388957 9020060265 2169434122 2513349261 2582295831 0662383677 5650571372 5539991419 0785003056 9992292209 0786444576 3570618143 4455743457 5657903472 4741521725 6895323033 0404456993 3828914275 7358347336 5364462764 1767934302 0226146948 7088711820 0551558952 1883501841 5563782337 3140349473 9051010237 3128258329 0126235880 5422499378 2371673724 1271463523 5699146744 7472510250 4139454737 3153079012 8657319446 1830521053 5829521812 5626418001 2799210508 9175520681 0272499584 4080127773 6586066119 4118028394 9948949108 7032912025 1727768232 4242010562 0067936428 6999518973 0030834872 8203160961 2455982277 8760520340 0261418732 2734909809 6215964181 0643746805 6276356853 5483150463 2725546550 0766874541 3421395042 3674411628 9787056785 4910183879 6958048309 0367793188 6789987469 6508214501 4217542898 2784633495 0263542642 1706860474 5483563674 9972406874 2952282122 9361875383 5555793853 3323674321 8473057894 9794487251 9618229533 8883834769 9322409838 0638618144 1275245643 9408083883 7638738405 6233281978 5523662143 1843483963 3212536323 7184387594 5540901612 0611677752 9422798491 4277774202 4641775039 0005448886 0174183933 4005305591 7768710788 5009806169 4233288770 4525834972 1984699754 3373185408 7619307767 0567144968 8388977085 0785409261 6196862452 6688459462 0210226133 9580022845 9694903741 0885283969 1791117322 3123932035 6589829269 9046911196 5435108800 5573409600 0489351593 9552054341 2498555709 0324522206 8099969301 6240633306 7633160505 1023146065 5220450164 9394203464 7941870734 6423549475 3457952396 8621778871 8867900221 9698543245 7268848712 4825496168 0127666493 3434524801 6865104481 1693064999 7044257223 3104154525 0448835960 4359309210 6546380660 9352375063 1044579003 1292375626 1860021756 7168327617 0132777711 5455419932 7215923605 0017857216 4523192328 8568274186 6222529089 7597889289 9056602436 0395401808 3173221536 0084377685 3242719030 8902022380 0224522736 8629133991 8792328024 5643263720 7672583953 1471378186 8533547602 2021407579 7860902171 3235152157 4045726346 1207454282 6448881745 9053934101 2406840188 3588022115 4107866022 5735170221 9703570147 8726693643 6964294405 1033686011 8974790091 1107374965 2317409809 8487840318 0330557570 5052130469
• z₄= -92465 8258052938 8203625142 8351665224 8586030202 6960590582 4173825140 1243088985 1943177595 7689022209 3412231241 3374313483 1540401666 1302817105 1631111976 7137803607 3674728856 6186275517 6707145786 8439330886 2435690704 4052456191 9378343821 2777122673 2903711512 9996374287 7672486823 3504025718 2900702496 9507066866 7762764493 5463484678 6147383917 3442605712 9151892861 7941975696 7952515710 1795195270 9094372841 8575624002 2788256727 2895570869 1556016032 9090856682 5339850228 7324722354 7876903229 8988559975 6445442913 6424784197 3697106369 9325878265 4112686932 2500108054 2145976782 6747936467 2759772477 9685993832 6162249530 5958945635 4346927065 6341650219 1285109033 2354166928 7884221974 7337697039 0063259795 6415580233 4149383399 3817595796 7630970900 3285531360 6798559385 4937599700 7047260074 8850676022 4280789421 2519004483 1970682421 8333846590 6178381198 2264369206 0037288451 1944547719 9151442243 7263592349 8731309633 5151147127 9948806635 4446894973 5234658345 0148807236 1747314700 3590792191 4433562095 5354685231 3847768704 1336500305 0667231692 7724180264 4210311681 4670792081 9845396322 0213303181 1456236244 8202702134 9156064764 4718100193 3938766554 0250060456 7323954698 8134870588 8570575570 6006813793 2141810169 7304482857 5791440313 8621391132 9738451854 2485172938 2070177355 8091896942 5059331396 9634879807 5801357849 7482074284 2178990841 9802783395 3600175760 3882344901 0712732587 1659115953 9728654591 3949680530 6658971324 0280704053 3153762637 3208309785 0957646842 7619022184 4066756988 2643089409 5932486216 9256481608 7228346070 4901339350 6545284657 4614357692 0684032711 0339330092 3241425101 5563844056 9616693922 9641505306 9160971360 9123244064 6398089664 9618728457 7229028974 6413184268 4325586864 6535620602

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.